Shortest path in DAG

Graphs Hard Problems Hard

A practical application of this programming problem lies in routing and navigation software, such as Google Maps or Waze
The "Directed Acyclic Graph" represents the map's network of roads, with the "vertices" representing intersections and the "edges" representing the roads themselves
The algorithm to find the "shortest path" from a source (user's starting point) to all vertices (possible destinations) is a fundamental operation of these services
This would allow them to provide real-time directions and traffic updates, indicating the fastest route to the destination
If a path can't be found (represented by '-1'), it means that destination is unreachable from the current location

Given a Directed Acyclic Graph of N vertices from 0 to N-1 and M edges and a 2D Integer array edges, where there is a directed edge from vertex edge[i][0] to vertex edge[i][1] with a distance of edge[i][2] for all i.

Find the shortest path from source vertex to all the vertices and if it is impossible to reach any vertex, then return -1 for that vertex. The source vertex is assumed to be 0.

Examples:

Input: N = 4, M = 2 edge = [[0,1,2],[0,2,1]]

Output: 0 2 1 -1

Explanation:

Shortest path from 0 to 1 is 0->1 with edge weight 2.

Shortest path from 0 to 2 is 0->2 with edge weight 1.

There is no way we can reach 3, so it's -1 for 3.

Input: N = 6, M = 7 edge = [[0,1,2],[0,4,1],[4,5,4],[4,2,2],[1,2,3],[2,3,6],[5,3,1]]

Output: 0 2 3 6 1 5

Explanation:

Shortest path from 0 to 1 is 0->1 with edge weight 2.

Shortest path from 0 to 2 is 0->4->2 with edge weight 1+2=3.

Shortest path from 0 to 3 is 0->4->5->3 with edge weight 1+4+1=6.

Shortest path from 0 to 4 is 0->4 with edge weight 1.

Shortest path from 0 to 5 is 0->4->5 with edge weight 1+4=5.

Input: N = 3, M = 3 edge = [[0, 1, 4], [0, 2, 2], [1, 2, 5]]

Constraints

1 ≤ N,M ≤ 5*10⁴
0 ≤ edge[i][0],edge[i][1] < N-1
1 ≤ edge[i][2] < 10⁴

Hints

"Perform Depth-First Search (DFS) to determine the order. If a back-edge is detected during DFS traversal, it means a cycle exists, and the order is invalid."

Company Tags

Oracle Boston Consulting Group Databricks Twilio Texas Instruments Philips Healthcare Uber Optum McKinsey & Company Broadcom Lyft Snowflake Cerner Bungie Zoho Ernst & Young Activision Blizzard Electronic Arts Intel Roblox Morgan Stanley Seagate Technology Shopify Freshworks Medtronic Google Microsoft Amazon Meta Apple Netflix Adobe

Editorial

Intuition:

Finding the shortest path to a node is easy if the shortest paths to all the nodes that can precede it are known. Processing the nodes in topological order ensures that by the time a node is reached, all the nodes that can precede have already been processed, reducing the computation time significantly.
Thus, for the solution, the nodes will be traversed sequentially according to their reachability from the source.

Once the topological ordering is obtained, all the nodes can be processed one by one. For every vertex being processed, we update the distances of its adjacent using the distance of the current vertex.

Approach:

The graph is represented using an adjacency list where each node points to its neighboring nodes along with the edge weights.
Perform a Depth First Search (DFS) to obtain a topological order of the nodes, ensuring each node is processed before its successors.
Initialize a distance array with a high value (indicating infinity) for all nodes except the source node, which is set to zero.
Using the topological order, update the shortest distance for each node by relaxing the edges, meaning if a shorter path is found to a neighboring node, update its distance.
Mark nodes that remain unreachable with a distance of -1. Return the shortest distances from the source to all nodes.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:

    // Function to perform DFS traversal
    void topoSort(int node, vector <pair<int,int>> adj[],
                  vector<bool> &vis, stack <int> & st) {
                
        // Mark the node as visited 
        vis[node] = 1;
        
        // Traverse all the neighbors
        for (auto it: adj[node]) {
            
            // Get the node
            int v = it.first;
            
            // If not visited, recursively perform DFS.
            if (!vis[v]) {
                topoSort(v, adj, vis, st);
            }
        }
        
        /* Add the current node to stack 
        once all the nodes connected to it 
        have been processed */
        st.push(node);
    }
    
public:

    /* Function to get the shortest path 
    for every node from source node 0 */
    vector<int> shortestPath(int N, int M, 
            vector<vector<int>> &edges) {

        // To store the graph
        vector <pair<int,int>> adj[N];
        
        // Add edges to the graph
        for (int i = 0; i < M; i++) {
            int u = edges[i][0]; // node 1
            int v = edges[i][1]; // node 2
            int wt = edges[i][2]; // edge weight
            
            // Add the weighted edge 
            adj[u].push_back({v, wt}); 
        }
        
        
        // Visited array
        vector<bool> vis(N, false);
        
        /* Stack to facilitate topological 
        sorting using DFS traversal */
        stack <int> st;
        
        // Get the topological ordering
        for (int i = 0; i < N; i++) {
            if (!vis[i]) {
              topoSort(i, adj, vis, st);
            }
        }
        
        // Distance array to store the shortest paths
        vector <int> dist(N, 1e9);
        
        // Distance of source node to itself is zero
        dist[0] = 0;
        
        // Until the stack is not empty
        while (!st.empty()) {
            
            // Get the node from top of stack
            int node = st.top();
            st.pop();
            
            // Update the distances of adjacent nodes
            for (auto it: adj[node]) {
                int v = it.first; // adjacent node
                int wt = it.second; // edge weight
                
                /* Relaxing the edge, i.e., if a 
                shorter path is found, update its
                distance to new shorter distance*/
                if (dist[node] + wt < dist[v]) {
                    dist[v] = wt + dist[node];
                }
            }
        }
        
        /* If a node is unreachable, 
        updating its distance to -1 */
        for (int i = 0; i < N; i++) {
            if (dist[i] == 1e9) 
                dist[i] = -1;
        }
        
        // Return the result
        return dist;
    }
};

int main() {
    
    int N = 4, M = 2;
    vector<vector<int>> edges = {
        {0, 1, 2}, {0, 2, 1}  
    };
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to determine order of 
	letters based on alien dictionary */
    vector<int> ans = sol.shortestPath(N, M, edges);
    
    // Output
    cout << "The shortest distance of every node from source node is:\n";
    for(int i=0; i < N; i++) {
        cout << ans[i] << " ";
    }
    
    return 0;
}
import java.util.*;

class Solution {
    // Pair implementation
    static class Pair {
        int first, second;

        Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }
    
    private void topoSort(int node, List<List<Pair>> adj,
                          boolean[] vis, Stack<Integer> st) {
        // Mark the node as visited 
        vis[node] = true;

        // Traverse all the neighbors
        for (Pair it : adj.get(node)) {

            // Get the node
            int v = it.first;

            // If not visited, recursively perform DFS
            if (!vis[v]) {
                topoSort(v, adj, vis, st);
            }
        }

        /* Add the current node to stack 
        once all the nodes connected to it 
        have been processed */
        st.push(node);
    }

    public int[] shortestPath(int N, int M, int[][] edges) {

        // To store the graph
        List<List<Pair>> adj = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            adj.add(new ArrayList<>());
        }

        // Add edges to the graph
        for (int i = 0; i < M; i++) {
            int u = edges[i][0]; // node 1
            int v = edges[i][1]; // node 2
            int wt = edges[i][2]; // edge weight

            // Add the weighted edge 
            adj.get(u).add(new Pair(v, wt));
        }

        // Visited array
        boolean[] vis = new boolean[N];

        /* Stack to facilitate topological 
        sorting using DFS traversal */
        Stack<Integer> st = new Stack<>();

        // Get the topological ordering
        for (int i = 0; i < N; i++) {
            if (!vis[i]) {
                topoSort(i, adj, vis, st);
            }
        }

        // Distance array to store the shortest paths
        int[] dist = new int[N];
        Arrays.fill(dist, (int)1e9);

        // Distance of source node to itself is zero
        dist[0] = 0;

        // Until the stack is not empty
        while (!st.isEmpty()) {

            // Get the node from top of stack
            int node = st.pop();

            // Update the distances of adjacent nodes
            for (Pair it : adj.get(node)) {
                int v = it.first; // adjacent node
                int wt = it.second; // edge weight

                /* Relaxing the edge, i.e., if a 
                shorter path is found, update its
                distance to new shorter distance */
                if (dist[node] + wt < dist[v]) {
                    dist[v] = wt + dist[node];
                }
            }
        }

        /* If a node is unreachable, 
        updating its distance to -1 */
        for (int i = 0; i < N; i++) {
            if (dist[i] == (int)1e9)
                dist[i] = -1;
        }

        // Return the result
        return dist;
    }
}

class Main {
    public static void main(String[] args) {

        int N = 4, M = 2;
        int[][] edges = {
            {0, 1, 2}, {0, 2, 1}
        };

        // Creating an instance of Solution class
        Solution sol = new Solution();

        // Function call to determine order of 
        // letters based on alien dictionary
        int[] ans = sol.shortestPath(N, M, edges);

        // Output
        System.out.println("The shortest distance of every node from source node is:");
        for (int i : ans) {
            System.out.print(i + " ");
        }
    }
}
from collections import defaultdict
from typing import List

class Solution:
    
    # Function to perform DFS traversal
    def topoSort(self, node, adj, vis, st):
        # Mark the node as visited 
        vis[node] = True
        
        # Traverse all the neighbors
        for v, _ in adj[node]:
            
            # If not visited, recursively perform DFS
            if not vis[v]:
                self.topoSort(v, adj, vis, st)
        
        """ Add the current node to stack 
        once all the nodes connected to it 
        have been processed """
        st.append(node)
    
    # Function to get the shortest path 
    # for every node from source node 0
    def shortestPath(self, N, M, edges):
        
        # To store the graph
        adj = defaultdict(list)
        
        # Add edges to the graph
        for u, v, wt in edges:
            # Add the weighted edge 
            adj[u].append((v, wt))
        
        # Visited array
        vis = [False] * N
        
        """ Stack to facilitate topological 
        sorting using DFS traversal """
        st = []
        
        # Get the topological ordering
        for i in range(N):
            if not vis[i]:
                self.topoSort(i, adj, vis, st)
        
        # Distance array to store the shortest paths
        dist = [1e9] * N
        
        # Distance of source node to itself is zero
        dist[0] = 0
        
        # Until the stack is not empty
        while st:
            
            # Get the node from top of stack
            node = st.pop()
            
            # Update the distances of adjacent nodes
            for v, wt in adj[node]:
                """ Relaxing the edge, i.e., if a 
                shorter path is found, update its
                distance to new shorter distance """
                if dist[node] + wt < dist[v]:
                    dist[v] = wt + dist[node]
        
        """ If a node is unreachable, 
        updating its distance to -1 """
        for i in range(N):
            if dist[i] == 1e9:
                dist[i] = -1
        
        # Return the result
        return dist


# Example usage
N, M = 4, 2
edges = [
    [0, 1, 2], [0, 2, 1]
]

# Creating an instance of Solution class
sol = Solution()

# Function call to determine order of 
# letters based on alien dictionary
ans = sol.shortestPath(N, M, edges)

# Output
print("The shortest distance of every node from source node is:")
print(*ans)
class Solution {
    
    // Function to perform DFS traversal
    topoSort(node, adj, vis, st) {
                
        // Mark the node as visited 
        vis[node] = true;
        
        // Traverse all the neighbors
        for (let it of adj[node]) {
            
            // Get the node
            let v = it[0];
            
            // If not visited, recursively perform DFS.
            if (!vis[v]) {
                this.topoSort(v, adj, vis, st);
            }
        }
        
        /* Add the current node to stack 
        once all the nodes connected to it 
        have been processed */
        st.push(node);
    }
    
    /* Function to get the shortest path 
    for every node from source node 0 */
    shortestPath(N, M, edges) {
        
        // To store the graph
        let adj = Array.from({ length: N }, () => []);
        
        // Add edges to the graph
        for (let i = 0; i < M; i++) {
            let u = edges[i][0]; // node 1
            let v = edges[i][1]; // node 2
            let wt = edges[i][2]; // edge weight
            
            // Add the weighted edge 
            adj[u].push([v, wt]);
        }
        
        // Visited array
        let vis = new Array(N).fill(false);
        
        /* Stack to facilitate topological 
        sorting using DFS traversal */
        let st = [];
        
        // Get the topological ordering
        for (let i = 0; i < N; i++) {
            if (!vis[i]) {
                this.topoSort(i, adj, vis, st);
            }
        }
        
        // Distance array to store the shortest paths
        let dist = new Array(N).fill(1e9);
        
        // Distance of source node to itself is zero
        dist[0] = 0;
        
        // Until the stack is not empty
        while (st.length > 0) {
            
            // Get the node from top of stack
            let node = st.pop();
            
            // Update the distances of adjacent nodes
            for (let it of adj[node]) {
                let v = it[0]; // adjacent node
                let wt = it[1]; // edge weight
                
                /* Relaxing the edge, i.e., if a 
                shorter path is found, update its
                distance to new shorter distance*/
                if (dist[node] + wt < dist[v]) {
                    dist[v] = wt + dist[node];
                }
            }
        }
        
        /* If a node is unreachable, 
        updating its distance to -1 */
        for (let i = 0; i < N; i++) {
            if (dist[i] === 1e9) 
                dist[i] = -1;
        }
        
        // Return the result
        return dist;
    }
}

// Example usage
let N = 4, M = 2;
let edges = [
    [0, 1, 2], [0, 2, 1]
];

// Creating an instance of Solution class
let sol = new Solution();

// Function call to determine order of letters based on alien dictionary
let ans = sol.shortestPath(N, M, edges);

// Output
console.log("The shortest distance of every node from source node is:");
for (let i = 0; i < N; i++) {
    console.log(ans[i] + " ");
}

Complexity Analysis:

Time Complexity: O(N+M)

Topological Sorting takes O(N+M) time.
To relax all the vertices, each node and its adjacent nodes are traversed taking O(M) time.

Space Complexity: O(N+M)

Storing the graph takes O(M) space.
The stack storing the topological ordering takes O(N) space.
The topological sorting algorithm uses O(N) space due to visited array and recursion stack space.

Code

Problem List