Given a directed acyclic graph (DAG) and a source vertex, find the cost of shortest path from source vertex to all other vertices present in the graph. If vertex can’t be reached from given source vertex, print its distance as infinity.

For example, consider below DAG,

The shortest distance of source vertex 7 to

vertex 0 is 6 (7 —> 0)

vertex 1 is -2 (7 —> 5 —> 1)

vertex 2 is -6 (7 —> 5 —> 1 —> 2)

vertex 3 is 4 (7 —> 3)

vertex 4 is -1 (7 —> 5 —> 1 —> 4)

vertex 5 is -4 (7 —> 5)

vertex 6 is 6 (7 —> 5 —> 1 —> 6)

We know that a Topological Sort of a directed acyclic graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

We can use topological sort to solve this problem. When we consider a vertex u in topological order, it is guaranteed that we have considered every incoming edge to it. Now for each vertex v of the DAG in the topological order, we relax cost of its outgoing edges (update shortest path information). In order words since we have already found shortest path to vertex v, we can use that info to update shortest path of all its adjacent vertices. i.e.

for each vertex u in topological order

for each edge (u, v) with weight w

if distance[u] + w > distance[v]

distance[v] = distance[u] + w

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 |
#include <bits/stdc++.h> using namespace std; // Number of vertices in the graph #define N 8 // data structure to store graph edges struct Edge { int src, dest, weight; }; // class to represent a graph object class Graph { public: // A array of vectors to represent adjacency list vector<Edge> adjList[N]; // Constructor Graph(vector<Edge> edges) { // add edges to the directed graph for (unsigned i = 0; i < edges.size(); i++) { int src = edges[i].src; int dest = edges[i].dest; int weight = edges[i].weight; adjList[src].push_back({src, dest, weight}); } } }; // Perform DFS on graph and set departure time of all // vertices of the graph int DFS(Graph const &graph, int v, vector<bool> &discovered, vector<int> &departure, int& time) { // mark current node as discovered discovered[v] = true; // set arrival time - not needed // time++; // do for every edge (v -> u) for (Edge e : graph.adjList[v]) { int u = e.dest; // u is not discovered if (!discovered[u]) DFS(graph, u, discovered, departure, time); } // ready to backtrack // set departure time of vertex v departure[time] = v; time++; } // The function performs topological sort on a given DAG // and then finds out the shortest distance of all vertices // from given source by running one pass of Bellman-Ford // algorithm on edges of vertices in topological order void findShortestDistance(Graph const& graph, int source) { // departure[] stores vertex number having its departure // time equal to the index of it vector<int> departure(N, -1); // stores vertex is discovered or not vector<bool> discovered(N); int time = 0; // perform DFS on all undiscovered vertices for (int i = 0; i < N; i++) if (!discovered[i]) DFS(graph, i, discovered, departure, time); vector<int> cost(N, INT_MAX); cost[source] = 0; // Process the vertices in topological order i.e. in order // of their decreasing departure time in DFS for (int i = N - 1; i >= 0; i--) { // for each vertex in topological order, // relax cost of its adjacent vertices int v = departure[i]; for (Edge e : graph.adjList[v]) { // edge e from v to u having weight w int u = e.dest; int w = e.weight; // if the distance to the destination u can be shortened by // taking the edge vu, then update cost to the new lower value if (cost[v] != INT_MAX && cost[v] + w < cost[u]) cost[u] = cost[v] + w; } } // print shortest paths for (int i = 0; i < N; i++) { cout << "\nShortest distance of source vertex " << source << " to vertex " << i << " is " << setw(2) << cost[i]; } } // Find the cost of Shortest Path in DAG int main() { // vector of graph edges as per above diagram vector<Edge> edges = { {0, 6, 2}, {1, 2, -4}, {1, 4, 1}, {1, 6, 8}, {3, 0, 3}, {3, 4, 5}, {5, 1, 2}, {7, 0, 6}, {7, 1, -1}, {7, 3, 4}, {7, 5, -4} }; // create a graph from edges Graph graph(edges); // source vertex int source = 7; // find Shortest distance of all vertices from given source findShortestDistance(graph, source); return 0; } |

**Output: **

Shortest distance of source vertex 7 to vertex 0 is 6

Shortest distance of source vertex 7 to vertex 1 is -2

Shortest distance of source vertex 7 to vertex 2 is -6

Shortest distance of source vertex 7 to vertex 3 is 4

Shortest distance of source vertex 7 to vertex 4 is -1

Shortest distance of source vertex 7 to vertex 5 is -4

Shortest distance of source vertex 7 to vertex 6 is 6

Shortest distance of source vertex 7 to vertex 7 is 0

Time complexity of above solution is O(n + m) where n is number of vertices and e is number of edges in the graph.

A related problem is to find the **longest paths from given source vertex to all other vertices present in the graph**. We can easily solve this problem by following above logic as well. The idea is to consider negative weights of the edges in the graph and find the shortest path from given source in the graph. Then the cost of longest path will be just negative of its cost of shortest path for any given vertex.

Check what Wikipedia has to say for Acyclic graphs –

*A longest path between two given vertices s and t in a weighted graph G is the same thing as a shortest path in a graph – G derived from G by changing every weight to its negation. Therefore, if shortest paths can be found in -G, then longest paths can also be found in G. For most graphs, this transformation is not useful because it creates cycles of negative length in -G. But if G is a directed acyclic graph, then no negative cycles can be created, and a longest path in G can be found in linear time by applying a linear time algorithm for shortest paths in -G, which is also a directed acyclic graph*

The implementation can be seen here.

**References:** https://en.wikipedia.org/wiki/Topological_sorting#Application_to_shortest_path_finding

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply