Кратчайший путь в направленном ациклическом графе от источника до всех остальных узлов может быть достигнут с помощью топологической сортировки с последующим обходом графа по ширине (нам потребуется стек для хранения топологической сортировки и на стеке мы будем выполнять поиск по ширине для получения кратчайшего расстояния.
Причина использования топологической сортировки проста, мы экономим много времени, начиная с начальной точки, вместо того, чтобы начинать с любой случайной точки. Поскольку через 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();
}
}