Кратчайшее расстояние от источника до всех остальных узлов в направленном ациклическом графе

Кратчайший путь в направленном ациклическом графе от источника до всех остальных узлов может быть достигнут с помощью топологической сортировки с последующим обходом графа по ширине (нам потребуется стек для хранения топологической сортировки и на стеке мы будем выполнять поиск по ширине для получения кратчайшего расстояния.
Причина использования топологической сортировки проста, мы экономим много времени, начиная с начальной точки, вместо того, чтобы начинать с любой случайной точки. Поскольку через topo sort мы знаем начальную точку, следовательно, использование topo sort становится оптимальным!)

Решение: Временная сложность составляет 2*O(n+e), где n — узлы и e — ребра 2, так как o(n+e) для topo sort и o(n+e) для поиска по ширине.
Пространственная сложность составляет o(n) для посещенных, o(n) для расстояния, o(n) для стекового пространства сортировки topo и o(n) для Stack<Integer> = 4*o(n).


 private int[] shortestPath(ArrayList<ArrayList<Pair>> adj,int N){
    // here pair will store edge weight between two nodes having and edge
    //example if u and v have and edge with weight 3, => u.add(new Pair(v,5)); like this.
    // first we will have to identify the source or the starting point in the graph
    // so that distance of traversing all other nodes will be smaller from this node.
    // for this we will use topo sorting
    Stack<Integer> stack = new Stack<>();
    int visited[] = new int[N];
    for(int i =0;i<N;i++){
        if(visited[i] ==0){
            dfs(i,adj,visited,stack);
        }
    }
    //now the stack will have topo sorted nodes of the graph.
    //now we will do breadth first search for getting shortest path from source to 
    // all the other nodes in the graph.
    int distance[] = new int[N];
    // source node will be
    int source = stack.peek();
    Arrays.fill(distance,Integer.MAX_VALUE);// distance of all other nodes from the source will be infinite initially.
    distance[source] = 0;// source distance will be zero 
    while(!stack.isEmpty()){
        Integer  i = stack.pop();
        if(distance[i]!=Integer.MAX_VALUE){ // just to make sure that that current node is reachable
            for(Pair pair : adj.get(i)){
                if(distance[pair.getKey()]> distance[i]+ pair.getValue()){
                    distance[pair.getKey()] = distance[i] + pair.getValue();
                }
            }
        }
    }
    return distance; /// for any node if the distance comes as Integer.MAX_VALUE then that node is not reachable from the source node.
}

public void dfs(int node, ArrayList<ArrayList<Pair>> adj, int[] visited,Stack<Integer> stack){
    visited[node] = 1;
    for(Pair i : adj.get(node)){
        if(visited[i.getKey()] ==0) dfs(i.getKey(),adj,visited,stack);
    }
    stack.push(node);
}
class Pair{
    private int key;
    private int value;
    public Pair(){
        super();
    }
    public Pair(int i,int j){
        this.key = i;
        this.value =j;
    }
    public int getKey(){
        return this.key;
    }
    public int getValue(){
        return this.getValue();
    }
}
Вход в полноэкранный режим Выход из полноэкранного режима

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