Shortest path in a directed acyclic graph

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:

• Path With Minimum Effort
• Unique Paths
• Longest Path In A DAG 

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, Uber, Microsoft, etc., on Coding Ninjas Studio.