Coding

Shortest path in DAG

Asked at

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

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.

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]]

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

cpp

class Solution {
    public:
    vector < int > shortestPath(int N, int M, vector < vector < int >> & edges) {
    }
};

java

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

python

class Solution:
    def shortestPath(self, N, M, edges):

javascript

class Solution {
    shortestPath(N, M, edges) {
  
    }
}

csharp

class Solution
{
    public List<int> ShortestPath(int N, int M, List<List<int>> edges) {

    }
}

func shortestPath(N int, M int, edges [][]int) []int {
	
}

Stuck? Show a way to structure it+

01Confirm the graph is acyclic and choose a source
02Produce a topological order
03Relax outgoing weighted edges only from reachable nodes
04Convert remaining infinity values to the requested unreachable marker

Reference answer

Start by restating the input contract for Shortest path in DAG and testing the smallest boundary case before choosing the algorithm. Topologically order the DAG, initialize source distance to zero and all others to infinity, then relax each outgoing edge in topological order. Once a node is processed, no later path can improve it because all incoming predecessors came earlier. Explain the invariant while coding, then show how each update preserves it. Topological sorting and one relaxation per edge take O(V + E) time and O(V) auxiliary space beyond the graph. Walk through one nontrivial example aloud so the interviewer can see why the method reaches the intended result. Finally, call out input assumptions and failure cases rather than silently relying on them. A clean implementation should keep state local, use descriptive names, and avoid work that the invariant makes unnecessary.

Then expect these follow-ups

Why does topological order make one pass sufficient?
Tests: correctness reasoning
How would you reconstruct paths?
Tests: implementation extension

Hiring now

Linkedin has 196 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Engineer - Systems and Infrastructure
Mountain View, CA, United States
Lead Account Executive, Large Customer, Financial Services - LinkedIn Marketing Solutions
Chicago, IL, United States
Director, LinkedIn Pulse Digital Platform
New York, NY, United States

Or practice this question first

Next question