Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Approach
2.1.
PseudoCode
3.
Approach(Efficient)
3.1.
How is it better than Bellman-Ford?
3.2.
CODE IN C++(Efficient)
4.
Frequently Asked Questions
4.1.
What is the shortest path algorithm in directed graph?
4.2.
Which algorithm is best for shortest path?
4.3.
What is meant by directed acyclic graph?
4.4.
What is the best shortest path algorithm for weighted graph?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Shortest path in a directed acyclic graph

Author aniket verma
37 upvotes
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

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 Algorithm, BFS, and topological sorting. Without knowing these basic algorithms and data structures, jumping on to the shortest path problems in graphs is not recommended. 

Shortest path in a directed acyclic graph

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,
 

directed acyclic graph image

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 a 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 is the shortest path algorithm in directed graph?

The shortest path algorithm in a directed graph is an algorithm which is used to find the most efficient path between two nodes while considering edge directions. Dijkstra's algorithm and Bellman-Ford algorithm are commonly used.

Which algorithm is best for shortest path?

The best shortest path algorithm depends on the specific graph characteristics. Dijkstra's algorithm is efficient for non-negative weighted graphs, while Bellman-Ford works with negative weights but is slower.

What is meant by directed acyclic graph?

A directed acyclic graph (DAG) is a graph structure without any cycles, where edges have a one-way direction. DAGs are useful for modelling dependencies and scheduling tasks.

What is the best shortest path algorithm for weighted graph?

Dijkstra's algorithm is considered the best choice for weighted graphs when all edge weights are non-negative. However, for graphs with negative weights, Bellman-Ford is more suitable.

Conclusion

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. 

Recommended Problems:

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 Coding Ninjas Studio.

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, UberMicrosoft, etc., on Coding Ninjas Studio.

Previous article
Understanding Stock Span
Next article
Shortest Path in an Unweighted Graph
Live masterclass