Directed Acyclic Graph에서 소스에서 다른 모든 노드까지의 최단 거리

Shortest path 소스에서 다른 모든 노드로의 Directed Acyclic graph 토폴로지 정렬과 그래프의 너비 우선 순회를 사용하여 달성할 수 있습니다(토폴로지 정렬을 저장하려면 스택이 필요하고 스택에서 너비 우선 검색을 수행하여 가져오기 최단거리.
topo 정렬을 사용하는 이유는 간단합니다. 임의의 지점에서 시작하는 대신 시작 지점에서 시작하여 많은 시간을 절약할 수 있습니다. topo sort를 통해 알기 때문에 시작점을 알게 되므로 topo sort를 사용하는 것이 최적이 됩니다!)

솔루션: 시간 복잡도는 2*O(n+e)입니다. 여기서 n는 노드이고 e는 에지 2입니다. 왜냐하면 topo 정렬의 경우 o(n+e)이고 너비 우선 검색의 경우 o(n+e)이기 때문입니다.
공간 복잡성은 방문의 경우 o(n), 거리의 경우 o(n), topo 정렬의 스택 공간의 경우 o(n), 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();
    }
}