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 131 132 |
#include <iostream> #include <vector> #include <climits> #include <iomanip> using namespace std; // data structure to store graph edges struct Edge { int src, dest, weight; }; // class to represent a graph object class Graph { public: // An array of vectors to represent adjacency list vector<Edge> *adjList; // Constructor Graph(vector<Edge> const &edges, int N) { // allocate memory adjList = new vector<Edge>[N]; // add edges to the directed graph for (Edge const &edge: edges) { adjList[edge.src].push_back(edge); } } }; // 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, int N) { // 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 << "Shortest distance of source vertex " << source << " to vertex " << i << " is " << setw(2) << cost[i] << '\n'; } } // 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} }; // Number of nodes in the graph int N = 8; // create a graph from edges Graph graph(edges, N); // source vertex int source = 7; // find Shortest distance of all vertices from given source findShortestDistance(graph, source, N); return 0; } |

## Java

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 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 |
import java.util.*; // Data structure to store graph edges class Edge { int source, dest, weight; public Edge(int source, int dest, int weight) { this.source = source; this.dest = dest; this.weight = weight; } }; // Class to represent a graph object class Graph { // An array of Lists to represent adjacency list List<List<Edge>> adjList = null; // Constructor Graph(List<Edge> edges, int N) { adjList = new ArrayList<>(N); for (int i = 0; i < N; i++) { adjList.add(i, new ArrayList<>()); } // add edges to the undirected graph for (Edge edge: edges) { adjList.get(edge.source).add(edge); } } } class DFSUtil { // Perform DFS on graph and set departure time of all // vertices of the graph private static int DFS(Graph graph, int v, boolean[] discovered, 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 edge: graph.adjList.get(v)) { int u = edge.dest; // u is not discovered if (!discovered[u]) time = DFS(graph, u, discovered, departure, time); } // ready to backtrack // set departure time of vertex v departure[time] = v; time++; return 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 public static void findShortestDistance(Graph graph, int source, int N) { // departure[] stores vertex number having its departure // time equal to the index of it int[] departure = new int[N]; Arrays.fill(departure, -1); // stores vertex is discovered or not boolean[] discovered = new boolean[N]; int time = 0; // perform DFS on all undiscovered vertices for (int i = 0; i < N; i++) if (!discovered[i]) time = DFS(graph, i, discovered, departure, time); int[] cost = new int[N]; Arrays.fill(cost, Integer.MAX_VALUE); 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.get(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, update cost to the new lower value if (cost[v] != Integer.MAX_VALUE && cost[v] + w < cost[u]) cost[u] = cost[v] + w; } } // print shortest paths for (int i = 0; i < N; i++) { System.out.println("Shortest distance of source vertex " + source + " to vertex " + i + " is " + cost[i]); } } // Find the cost of Shortest Path in DAG public static void main(String[] args) { // vector of graph edges as per above diagram List<Edge> edges = Arrays.asList( new Edge(0, 6, 2), new Edge(1, 2, -4), new Edge(1, 4, 1), new Edge(1, 6, 8), new Edge(3, 0, 3), new Edge(3, 4, 5), new Edge(5, 1, 2), new Edge(7, 0, 6), new Edge(7, 1, -1), new Edge(7, 3, 4), new Edge(7, 5, -4) ); // Set number of vertices in the graph final int N = 8; // create a graph from given edges Graph graph = new Graph(edges, N); // source vertex int source = 7; // find Shortest distance of all vertices from given source findShortestDistance(graph, source, N); } } |

`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

The 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

Good one!