Shortest path in a directed acyclic graph

aniket verma
Last Updated: May 13, 2022

Introduction

In this blog, we will discuss how to find the shortest path in a directed acyclic graph. It is a very important problem to get a strong grip over graph-based algorithms and their applications and has also been asked in many interviews.

A common prerequisite before any graph problem is the knowledge of graphs and related terminologies such as recursion, stacks, queues, trees, and the 2 standard algorithms DFS, BFS, and topological sorting. Without knowing these basic algorithms and data structures, jumping on to the shortest path problems in graphs is not recommended. Nevertheless, we’ll try to cover each point in-depth that is required to find the shortest path in a directed acyclic graph.

What do we mean by the Shortest Path in a directed acyclic graph?

Well, it’s a trivial question, but still, for the sake of clarity, we’ll define that let

G = (V, E) be a directed graph with E edges and vertices.

Let T be the shortest path between any 2 vertices in the graph such that there is no other path in the graph between any 2 vertices whose sum of edge weights is less than T’s sum of edge weights. 

NOTE: shortest path between 2 vertices is defined only when the vertices are in the same graph, i.e., the graph should not be disconnected.

Let’s look at an example first.

Given a weighted DAG G,
 

Input:  Starting Node Src = 1 

Output: List of shortest distances denoting the shortest path from ‘Src’ to all other nodes in the DAG.

For the above DAG, we will return {INF, 0, 2, 6, 5, 3}

So the problem is to find the shortest path from a given source to All other nodes in the weighted DAG.

Approach

What is the first approach that comes to our mind? Don’t think about any optimizations for now. The first solution that will strike anybody’s mind is from the given ‘src’ node to find the shortest path to each node one by one. For all paths from source to a particular destination node, we will choose the shortest path.

Let’s walk through this solution in the above example. 

So the given Source node is 1. Say Tsrc - desti → denotes the ith path from the ‘src’ node to a particular destination node.

For dest = 0,

There is no path, so the shortest path has weight INF.

For dest = 1,

There is no external path, but the distance from ‘src’ - ‘src’ is trivial, i.e., = 0.

For dest  = 2,

T1 - 21 = 1 -> 2, it’s the only path from ‘src’ node to dest node, hence shortest path has weight = 2.  

For dest  = 3,

T1 - 31 = 1 -> 3, it has distance = 6

T1 - 32 = 1 -> 2 -> 3, it has distance = 9

So the shortest distance of the 2 paths is 6.

For dest  = 4,

T1 - 41 = 1 -> 3 -> 4, it has distance = 5

T1 - 42 = 1 -> 2 -> 3 -> 4, it has distance = 8

T1 - 43 = 1 -> 2 -> 4, it has distance = 6

So the shortest distance of the 3 paths is 5.

For dest  = 5,

T1 - 51 = 1 -> 2->5, it has distance = 4

T1 - 52 = 1 ->  3 -> 4 -> 5, it has distance = 3

T1 - 53 = 1 -> 2 -> 3 -> 4 -> 5, it has distance = 6

T1 - 54 = 1 -> 2 -> 4 -> 5, it has distance = 4

So the shortest distance of the 4 paths is 3.


So we will compute the distances from the given ‘src’ node to all other nodes in a similar manner as we walked through the example.

Hence now we can formulate our approach for the brute-force approach:

  1. For a particular node, compute distances of all possible paths from the given ‘src’ node.
  2. From the calculated distances, find the minimum of them.
  3. Repeat the same process for all the other nodes in the DAG

PseudoCode

# Assume that the function computeAllDistances(Src, Dest) returns all possible path distances from Src to Dest.

Algorithm

___________________________________________________________________
procedure ShortestPathInDAG(Graph G, Src):
___________________________________________________________________
1.   Shortest_path_distances ← empty list  # final list that will be returned
2.    for each vertex v in G.V do
3.       List_of_all_possible_path_dists ← computeAllDistances(G, Src, v)  
4.       If  List_of_all_possible_path_dists is not empty do
5.              Shortest_path_distances[v] ← min(List_of_all_possible_path_dists)
6.       end if 
7.       else 
8.       Shortest_path_distances[v] ← INF
9.       end else if
10.   return Shortest_path_distances
11.   end procedure
___________________________________________________________________

 

The above approach is undoubtedly not efficient, as you can see the repetitive computations being made for calculating distances for each node. Let’s look at some efficient algorithms which can solve the same problem efficiently.

Approach(Efficient)

Many of you must be aware of the Bellman-Ford algorithm, which can be used here to compute the shortest distances from a given ‘src’ node to all nodes in O(|V||E|). It is a very efficient algorithm relative to the brute-force algorithm.

Note that if you are trying to use Dijkstra here, it won’t work because the weighted DAG can also have negative weights.

Can we think of some better algorithm other than the Bellman-Ford algorithm?

If we can have an ordering of vertices, all nodes that are not reachable from the ‘src’ node are kept on the left side of the ‘src’ node, and all reachable nodes are kept on its right.

Why are we looking for such an order? Because we will not have to update the shortest path of the unreachable nodes. Another advantage is that from a vertex, we can relax all the edges connecting the other vertices. This process can be done for all vertices in this ordering one by one for all their respective edges.

The intuition behind this is that, since we will find the shortest distance from the ‘src’ node, the ‘src’ node will be present in this ordering before all nodes are reachable from the ‘src’ node. So all vertices which form edges with ‘src’ nodes will get updated first. Then all the other edges will get relaxed one by one while visiting the vertices in this ordering.

This will find the shortest distance from the ‘src’ node to all nodes.

The ordering which we have been using in this discussion is the Topological sorted ordering of a graph.     

How is it better than Bellman-Ford?

The topological ordering can be found in O(|V| + |E|) time. The rest of the relaxation steps will also take O(|V|+|E|) time (Why?) because we traverse the edges of each vertex and relax the edges one by one. Hence it will take O(|V|+|E|) time. Thus, the whole algorithm would run in O(|V|+|E|) time.


NOTE: if the graph had a cycle even if it had positive weights only, we couldn’t have used this topological sorted ordering algorithm because topological sorting does not exist for a cyclic graph.

Hence we have improved from a brute-force approach to an efficient approach.

Now let’s formulate our approach :

  1. Find the topological ordering from the ‘src’ node
  2. Now traverse the vertices in the ordering one by one.
  3. If there are some nodes in the ordering before the ‘src’ node, they are not reachable from the ‘src’ node, hence no need to update their distances from the ‘src’ node.
  4. Now for each vertex from the ‘src’ node in the ordering, relax its connecting edges one by one and update the distances of the other vertex connecting the edge with the current vertex if their respective edges get relaxed.
  5. Once all edges get relaxed, return the list of distances.  


CODE IN C++(Efficient)

//C++ program to find the Shortest Path in a DAG

#include <bits/stdc++.h>

using namespace std;

 

// Graph class implemented using an adjacency list

class Graph{

public:

    int V;  // Number of Vertices

    int E;  // Number of Edges

    vector<pair<int, int>> *adj; // adjacency list

    Graph(int num_vertices, int num_edges){

        this->V = num_vertices;

        this->E = num_edges;

        this->adj = new vector<pair<int, int>>[num_vertices];

    }

    

    // function to add Edge

    void addEdge(int u, int v, int w){

        adj[u].push_back({v, w});

    }

    

    // function that returns the topSort ordering of nodes in a graph

    vector<int> topSort(int src){

 

        //inDegree vector

        vector<int> indegree(V, 0);

 

        // update the indegree of each node in the graph

        for(int i=0;i<V;++i){

            for(pair<int, int> node:this->adj[i]){

                indegree[node.first]++;

            }

        }

 

        // queue 

        queue<int> q;

        

        // push all nodes with 0 in degree in the queue

        for(int i=0;i<V;++i){

            if(indegree[i]==0)

                q.push(i);

        }

        

        // vector to store topSortOrdering        

        vector<int> topSortOrdering;

        

        // run until queue is empty

        while(!q.empty()){

            

            // pop the front node

            int u = q.front();

            q.pop();

 

            // since it has 0 indegree it will occur before all elements 

            // with non-0 indegree currently

            topSortOrdering.push_back(u);

            

            // decrement the indegree of adjacent nodes of the popped node 

            // by 1

            for(pair<int, int> node:this->adj[u]){

                indegree[node.first]--;

                

                // if the indegree of the node is 0

                if(indegree[node.first]==0){

                    

                    // push it to the queue

                    q.push(node.first);

                }

            }

            

        }

        // return the topSortOrdering        

        return topSortOrdering;

    }

    

    //find all the shortest path distances

    void findShortestPathInDAG(int src){

        

        // distance vector from the src node

        vector<int> distances(V, INT_MAX);

        

        // find the topSort ordering        

        vector<int> topSortOrdering = topSort(src);

        

        // initially mark the distance from the source node to itself as 0

        distances[src]=0;

        

        // for each vertex in topSortOrdering

        for(int x:topSortOrdering){

            

            // if current vertex weight is not INT_MAXinity

            if(distances[x]!=INT_MAX){

                

                // traverse all the adjacent Edges

                for(pair<int, int> adjNode : this->adj[x]){

                    

                    // relax the edges

                    if(distances[adjNode.first] > distances[x]+adjNode.second){

                        distances[adjNode.first] = distances[x]+adjNode.second;

                    }

                }   

            }

        }

        

        // print the final distances

        

        cout<<"The distances from the src node are: ";

        for(int i=0;i<V;++i){

            if(distances[i]==INT_MAX) cout<<"INF ";

            else cout<<distances[i]<<" ";

        }

    }

    

};

int main() {

    // Number of Edges and Vertices

    int num_vertices = 6;

    int num_edges = 9;

 

    Graph G(num_vertices, num_edges); // Graph G

    

    // add all edges to graph

    G.addEdge(1, 3, 6);

    G.addEdge(1, 2, 2);

    G.addEdge(0, 1, 5);

    G.addEdge(0, 2, 3);

    G.addEdge(3, 4, -1);

    G.addEdge(2, 4, 4);

    G.addEdge(2, 5, 2);

    G.addEdge(2, 3, 7);

    G.addEdge(4, 5, -2);

 

    // compute the Shortest_path

    int src = 1; 

    G.findShortestPathInDAG(src);

    return 0;

}

Output

The distances from the src node are: INF 0 2 6 5 3 

Time Complexity: O(|V| + |E|)

Since we are computing the topological ordering of the nodes in the graph.

Space complexity: O(|V|) at the worst case, as the maximum nodes stored in the stack are O(|V|). Also, the distances being stored in the list of distances is of length |V|. Hence it takes O(|V|) space.

Hence we reached an efficient solution.

Frequently Asked Questions

What are the different algorithms for finding the topological sort of a DAG?

Answer)  Primarily there are 2 popular algorithms that are commonly used in finding the topological sort in a graph. The first one is the DFS based algorithm which uses a stack to maintain topological order. The second one is Kahn’s algorithm which uses the concept of node indegree.

Can there be multiple shortest paths in a Graph?

Answer) Yes, we can find multiple shortest paths in a Graph.

What is topological Sorting?

Answer) Topological Sorting is defined as a linear ordering of vertices of a graph G(V, E) such that for every directed edge e = (u, v), vertex u comes before the vertex v. It can be found only if the graph is a DAG. 

Key Takeaways

This article taught us how to find the shortest path in a directed acyclic graph by approaching the problem using a brute force approach followed by an efficient solution. We discussed solutions by walking through examples using illustrations, pseudocode, and then a proper code.

We hope you could take away critical techniques like analyzing problems by walking over the execution of the examples and finding out the redundant computations in brute force algorithms and how we can use typical graphical algorithms like Topological sorted order of a graph to solve a problem efficiently. 

Now, we recommend you practice problem sets based on the Shortest Path in a directed acyclic graph to master your fundamentals. You can get a wide range of questions similar to the problem Shortest path in a directed acyclic graph on CodeStudio

Was this article helpful ?
2 upvotes

Comments

No comments yet

Be the first to share what you think