Learn how to find single source shortest path in a weighted directed acyclic graph (DAG) in linear time. We explain topological sorting by DFS, step-by-step edge relaxation, include fully-commented Python code, a hand dry-run, and clear Big-O analysis.
Here’s the [Problem Link] to begin with.
1. What does the problem ask?
Given
V
– number of vertices labeled0 … V-1
E
– number of directed edgesedges[i] = [u, v, w]
– an edge fromu
tov
with positive weightw
return an array distance
where
distance[i]
= length of the shortest path from source 0 to vertex i- If vertex
i
is unreachable, store-1
.
Because the graph is a directed acyclic graph (DAG), there are no cycles.
2. Quick example
V = 6
edges = [
[0,1,2], [0,4,1],
[1,2,3], [4,2,2],
[2,3,6], [4,5,4], [5,3,1]
]
One set of shortest distances from source 0
is
[0, 2, 3, 6, 1, 5]
- 0 → 4 → 2 → … is cheaper than 0 → 1 → 2, etc.
- Vertex 3 is reached through 0 → 4 → 5 → 3 with total weight 6.
3. Intuition & approach
3.1 Why topological sort?
In a DAG you can line up vertices so that every edge goes left-to-right.
If you relax (update) edges in that order, by the time you process a vertex, its current distance is already the final shortest distance, no need for revisiting like Dijkstra or Bellman-Ford.
3.2 Algorithm steps
- Build an adjacency list
u → (v, w)
. - Topological sort all vertices with a DFS:
- Start DFS from every unvisited node.
- After finishing a node, push it onto a stack.
- When DFS ends, popping the stack yields a valid topo order.
- Single-source relaxation in topo order:
- Set
distance[src] = 0
, all others to∞
. - Pop vertices one by one.
- For each outgoing edge
u → v
with weightw
,- if
distance[u] + w < distance[v]
, updatedistance[v]
.
- if
- Set
- Post-process – convert every
∞
to-1
for unreachable nodes.
Because edges only go forward in the order, each one is relaxed exactly once, giving an O(V + E) time algorithm, the best you can hope for in a DAG.
4. Python code
from typing import List
class Solution:
# ---------- DFS for topological sort ----------
def dfs(self, node, stack, visited, adj_list):
visited[node] = 1
for adjNode, _ in adj_list[node]: # ignore weight during DFS
if visited[adjNode] == 0:
self.dfs(adjNode, stack, visited, adj_list)
stack.append(node) # post-order push
# ---------- main function ----------
def shortestPath(self, V: int, E: int, edges: List[List[int]]) -> List[int]:
# 1. Build adjacency list
adj_list = [[] for _ in range(V)]
for u, v, w in edges: # directed edge u -> v (weight w)
adj_list[u].append([v, w])
# 2. Topological sort by DFS
stack = []
visited = [0] * V
for i in range(V):
if visited[i] == 0:
self.dfs(i, stack, visited, adj_list)
# 3. Initialise distance array
distance = [float("inf")] * V
distance[0] = 0 # source vertex
# 4. Relax edges following topological order
while stack: # pop = left-to-right order
node = stack.pop()
if distance[node] == float("inf"): # unreachable so far
continue
for adjNode, w in adj_list[node]:
new_d = distance[node] + w
if new_d < distance[adjNode]:
distance[adjNode] = new_d
# 5. Replace infinity by -1 as problem demands
for i in range(V):
if distance[i] == float("inf"):
distance[i] = -1
return distance
5. Detailed step-by-step explanation
- Adjacency list – quickly lists
(neighbour, weight)
pairs for every vertex. dfs
routine – a classic post-order push guarantees parents appear after children in the stack, which reverses to topo order when popped.- Distance array –
∞
(herefloat('inf')
) means “not reached yet”. - Relaxation loop
- If the current node is still at
∞
, no shorter path can arise later because no incoming edges remain, so we skip it. - Otherwise explore its outgoing edges and update neighbours if we find a cheaper route.
- If the current node is still at
- Final loop converts unreached vertices to
-1
per the spec.
Because each vertex and edge is touched only once across DFS + relaxation, the algorithm is linear.
6. Dry run on the sample graph
Stack build (push order) | Stack after DFS | Pop order (topo) |
---|---|---|
5, 4, 2, 1, 3, 0 (example) | [5,4,2,1,3,0] | 0 → 3 → 1 → 2 → 4 → 5 |
Relaxation in that pop order produces the distances 0 2 3 6 1 5
.
7. Complexity analysis
Metric | Cost | Why |
---|---|---|
Time | O(V + E) | DFS visits each vertex/edge once; relaxation does the same |
Space | O(V + E) | Adjacency list + call stack + distance + visited arrays |
8.Conclusion
When the graph is a weighted DAG, the combination of topological sorting plus single-pass edge relaxation gives the fastest and simplest single-source shortest-path algorithm:
- Linear time – beats Dijkstra (needs a heap) and Bellman-Ford (multi-pass).
- In-place friendly – only a handful of arrays, no exotic data structures.
- Conceptually clear – once you trust topological order, relaxation is guaranteed to be final.
Next time you see a DAG with weights, reach straight for this technique!
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.