Shortest Path in Directed Acyclic Graph - GeeksforGeeks
Given a Weighted Directed Acyclic Graph and a source vertex in the graph, find the shortest paths from given source to all other vertices.
For a general weighted graph, we can calculate single source shortest distances in O(VE) time using Bellman–Ford Algorithm. For a graph with no negative weights, we can do better and calculate single source shortest distances in O(E + VLogV) time using Dijkstra’s algorithm. Can we do even better for Directed Acyclic Graph (DAG)? We can calculate single source shortest distances in O(V+E) time for DAGs. The idea is to use Topological Sorting.
We initialize distances to all vertices as infinite and distance to source as 0, then we find a topological sorting of the graph. Topological Sorting of a graph represents a linear ordering of the graph. Once we have topological order (or linear representation), we one by one process all vertices in topological order. For every vertex being processed, we update distances of its adjacent using distance of current vertex.
1) Initialize dist[] = {INF, INF, ….} and dist[s] = 0 where s is the source vertex.
2) Create a toplogical order of all vertices.
3) Do following for every vertex u in topological order.
………..Do following for every adjacent vertex v of u
………………if (dist[v] > dist[u] + weight(u, v))
………………………dist[v] = dist[u] + weight(u, v)
http://www.stoimen.com/blog/2012/10/28/computer-algorithms-shortest-path-in-a-directed-acyclic-graph/
1. Topologically sort G into L;
Given a Weighted Directed Acyclic Graph and a source vertex in the graph, find the shortest paths from given source to all other vertices.
For a general weighted graph, we can calculate single source shortest distances in O(VE) time using Bellman–Ford Algorithm. For a graph with no negative weights, we can do better and calculate single source shortest distances in O(E + VLogV) time using Dijkstra’s algorithm. Can we do even better for Directed Acyclic Graph (DAG)? We can calculate single source shortest distances in O(V+E) time for DAGs. The idea is to use Topological Sorting.
We initialize distances to all vertices as infinite and distance to source as 0, then we find a topological sorting of the graph. Topological Sorting of a graph represents a linear ordering of the graph. Once we have topological order (or linear representation), we one by one process all vertices in topological order. For every vertex being processed, we update distances of its adjacent using distance of current vertex.
1) Initialize dist[] = {INF, INF, ….} and dist[s] = 0 where s is the source vertex.
2) Create a toplogical order of all vertices.
3) Do following for every vertex u in topological order.
………..Do following for every adjacent vertex v of u
………………if (dist[v] > dist[u] + weight(u, v))
………………………dist[v] = dist[u] + weight(u, v)
http://www.stoimen.com/blog/2012/10/28/computer-algorithms-shortest-path-in-a-directed-acyclic-graph/
1. Topologically sort G into L;
2. Set the distance to the source to 0;
3. Set the distances to all other vertices to infinity;
4. For each vertex u in L
5. - Walk through all neighbors v of u;
6. - If dist(v) > dist(u) + w(u, v)
7. - Set dist(v) <- dist(u) + w(u, v);
Time Complexity: Time complexity of topological sorting is O(V+E). After finding topological order, the algorithm process all vertices and for every vertex, it runs a loop for all adjacent vertices. Total adjacent vertices in a graph is O(E). So the inner loop runs O(V+E) times. Therefore, overall time complexity of this algorithm is O(V+E).
http://stackoverflow.com/questions/1482619/shortest-path-for-a-dag
You have to take advantage of the information that a topological ordering gives you. Whenever you examine the node n in a topological ordering, you have the guarantee that you've already traversed every possible path to n.
DAG shortest paths
Solve the single-source shortest-path problem in a weighted directed acyclic graph by 1) doing a topological sort on the vertices by edge so vertices with no incoming edges are first and vertices with only incoming edges are last, 2) assign an infinite distance to every vertex (dist(v)=∞) and a zero distance to the source, and 3) for each vertex v in sorted order, for each outgoing edge e(v,u), if dist(v) + weight(e) < dist(u), set dist(u)=dist(v) + weight(e) and the predecessor of u to v.
// The function to find shortest paths from given vertex. It uses recursive // topologicalSortUtil() to get topological sorting of given graph.void Graph::shortestPath(int s){ stack<int> Stack; int dist[V]; // Mark all the vertices as not visited bool *visited = new bool[V]; for (int i = 0; i < V; i++) visited[i] = false; // Call the recursive helper function to store Topological Sort // starting from all vertices one by one for (int i = 0; i < V; i++) if (visited[i] == false) topologicalSortUtil(i, visited, Stack); // Initialize distances to all vertices as infinite and distance // to source as 0 for (int i = 0; i < V; i++) dist[i] = INF; dist[s] = 0; // Process vertices in topological order while (Stack.empty() == false) { // Get the next vertex from topological order int u = Stack.top(); Stack.pop(); // Update distances of all adjacent vertices list<AdjListNode>::iterator i; if (dist[u] != INF) { for (i = adj[u].begin(); i != adj[u].end(); ++i) if (dist[i->getV()] > dist[u] + i->getWeight()) dist[i->getV()] = dist[u] + i->getWeight(); } } // Print the calculated shortest distances for (int i = 0; i < V; i++) (dist[i] == INF)? cout << "INF ": cout << dist[i] << " ";}void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack){ // Mark the current node as visited visited[v] = true; // Recur for all the vertices adjacent to this vertex list<AdjListNode>::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) { AdjListNode node = *i; if (!visited[node.getV()]) topologicalSortUtil(node.getV(), visited, Stack); } // Push current vertex to stack which stores topological sort Stack.push(v);}
http://stackoverflow.com/questions/1482619/shortest-path-for-a-dag
You have to take advantage of the information that a topological ordering gives you. Whenever you examine the node n in a topological ordering, you have the guarantee that you've already traversed every possible path to n.
DAG shortest paths
Solve the single-source shortest-path problem in a weighted directed acyclic graph by 1) doing a topological sort on the vertices by edge so vertices with no incoming edges are first and vertices with only incoming edges are last, 2) assign an infinite distance to every vertex (dist(v)=∞) and a zero distance to the source, and 3) for each vertex v in sorted order, for each outgoing edge e(v,u), if dist(v) + weight(e) < dist(u), set dist(u)=dist(v) + weight(e) and the predecessor of u to v.
