Кратчайшее расстояние от источника до всех других узлов графа, где вес ребра равен 1 единице

 private void shortestPath(ArrayList<ArrayList<Integer>> adj,int N,int src){
    // we have to find the shortest Path from given source to all the 
    //other nodes in the graph.
    //let's initialize all the distances from the source as infinity.
    int distance[] = new int[N];
    for(int i =0;i<N;i++) distance[i] = Integer.MAX_VALUE;
    // we will put source distance as 0 as its a starting point
    distance[src] = 0;
    //now we will use breadth first search for finding the shortest distance from 
    //source to all other nodes
    Queue<Integer> q = new LinkedList<>();
        Integer node  = q.remove();
        //getting distance of all the adjacent nodes of current node
        for(Integer i : adj.get(node)){
            if(distance[i]> (distance[node] + 1)){
                distance[i] = distance[node]+1;// since distance of adjacent node will be distance of current node from source + unit distance i.e. 1
    for(int i =0;i<N;i++){
        System.out.println("distance of "+i+" from source " +src+" is "+ distance[i]);
Вход в полноэкранный режим Выход из полноэкранного режима

Оцените статью
Добавить комментарий