DevPath
Tracks

Graph Algorithms: Dijkstra, Topological Sort, Cycles, Components

Weighted shortest paths with Dijkstra, ordering tasks with topological sort, detecting cycles, and counting connected components.

advanced60 min#dijkstra#topological-sort#cycle-detection#connected-components#shortest-path

Prerequisites: Graphs: Representations, BFS and DFS, Heaps and Priority Queues

Why it matters

BFS and DFS tell you what is reachable. Real systems ask sharper questions. What is the cheapest route when roads have different lengths? In what order should a build system compile packages so that every dependency comes first? Can this set of course prerequisites ever be satisfied? How many separate clusters does this network contain? Four algorithms cover these cases, and each is a small twist on the traversals you already know.

Intuition

  • Dijkstra is BFS for weighted graphs. Instead of a plain queue, a priority queue always expands the closest unexplored vertex next. Once a vertex is the closest one left, nothing cheaper can reach it later, because all weights are non-negative.
  • Topological sort lines up the tasks of a directed acyclic graph (DAG) so every arrow points forward. Picture getting dressed: socks before shoes. Repeatedly do whatever has no unmet prerequisites.
  • Cycle detection asks whether following arrows can bring you back to where you started. If so, no valid order exists (shoes need socks, socks need shoes).
  • Connected components groups vertices into islands: start a traversal at any unvisited vertex, and everything it touches is one island.

How it works

Dijkstra. Keep dist[v], the best known distance from the source, initially infinity except the source at 0. Push (0, source) into a min-heap. Repeatedly pop the smallest (d, u). If d is larger than the recorded dist[u], it is a stale duplicate: skip it. Otherwise relax each edge (u, v, w): if d + w beats dist[v], update it and push the new pair. With a binary heap the cost is O((V + E) log V). It requires non-negative weights; with negative edges use Bellman-Ford. Dijkstra computes distances, and to recover the route you also store each vertex's predecessor when you relax.

41271A: 0B: infC: infD: inf
Dijkstra from A on a directed road graph. Each label shows the best known distance. Heap: (0, A). Pop (0, A).
step 1 / 6

Dijkstra on the same roads as the code. Labels are the best known distance so far, green is the vertex being expanded, amber vertices just received a new distance, and highlighted edges form the best route found so far. Notice B improves from 4 to 3 once the cheaper detour through C is discovered.

Topological sort (Kahn's algorithm). Compute each vertex's in-degree (number of incoming edges). Put all vertices with in-degree 0 in a queue. Pop one, append it to the output, and decrement the in-degree of each neighbor, queueing any that reach 0. If the output contains fewer than V vertices, the leftover vertices sit on a cycle. The DFS alternative records vertices in reverse finishing order. Both take O(V + E). The order is usually not unique.

0 (in 0)1 (in 1)2 (in 1)3 (in 2)4 (in 1)
Kahn on the dependency graph from the code. Each label shows the vertex and its in-degree (unmet prerequisites). Only 0 has in-degree 0. Queue: [0]. Output: [].
step 1 / 6

Kahn's algorithm. Green is the vertex just popped, amber vertices are waiting in the queue, faded vertices are already in the output, and highlighted edges are the ones just removed. The vertices come out in an order where every arrow points to the right.

Cycle detection.

  • Directed graphs: DFS with three colors. White is unvisited, gray is on the current recursion path, black is finished. Meeting a gray vertex means you found a back edge, a cycle. Meeting a black one is harmless (a different branch already finished). Kahn's algorithm doubles as a detector: fewer than V outputs means a cycle.

  • Undirected graphs: DFS or BFS, and a cycle exists if you reach a visited vertex that is not the one you just came from. Union-find (a later lesson) is another standard tool.

0 (white)1 (white)2 (white)
Directed graph 0 to 1 to 2 to 0 from the code. Colors: white is unvisited, gray is on the current path. Start the DFS at 0.
step 1 / 5

Three-color cycle detection on a directed triangle. Amber vertices are gray (on the DFS path), and the final highlighted edge is the back edge that reveals the cycle.

Connected components. For each vertex not yet seen, run a traversal and collect everything it reaches. The number of traversals started equals the number of components. O(V + E). For directed graphs, the analogous notion is strongly connected components, a more advanced topic.

0123456
7 vertices (0 to 6) and edges 0-1, 1-2 and 3-4, as in the code. No vertex has been visited, and the component count is 0.
step 1 / 5

Counting connected components. Green is the component the current traversal discovers, amber vertices belong to components found earlier. Each new traversal starts only at a vertex that is still unseen.

OperationTimeNotes
Dijkstra (binary heap)O((V + E) log V)Non-negative weights only
Topological sort (Kahn or DFS)O(V + E)DAG only
Cycle detection (DFS)O(V + E)Colors for directed graphs
Connected componentsO(V + E)One traversal per component
Extra spaceO(V)Distances, in-degrees, seen set

Code: all four

import heapq
import json
from collections import deque
 
def show(*xs):
    print(*(json.dumps(x, separators=(',', ':')) for x in xs))
 
def dijkstra(graph, src):
    dist = {src: 0}
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float("inf")):
            continue  # stale entry
        for v, w in graph.get(u, []):
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist
 
def topo_sort(n, edges):
    """Kahn's algorithm; returns None if the graph has a cycle."""
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else None
 
def has_cycle(n, edges):
    """Directed graph: DFS with colors 0=new, 1=on current path, 2=done."""
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
    color = [0] * n
    def visit(u):
        color[u] = 1
        for v in adj[u]:
            if color[v] == 1 or (color[v] == 0 and visit(v)):
                return True
        color[u] = 2
        return False
    return any(color[i] == 0 and visit(i) for i in range(n))
 
def components(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    seen, comps = set(), []
    for s in range(n):
        if s in seen:
            continue
        seen.add(s)
        stack, comp = [s], []
        while stack:
            u = stack.pop()
            comp.append(u)
            for v in adj[u]:
                if v not in seen:
                    seen.add(v)
                    stack.append(v)
        comps.append(sorted(comp))
    return comps
 
roads = {
    "A": [("B", 4), ("C", 1)],
    "C": [("B", 2), ("D", 7)],
    "B": [("D", 1)],
}
show(dijkstra(roads, "A"))
deps = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]
show(topo_sort(5, deps))
show(topo_sort(3, [(0, 1), (1, 2), (2, 0)]))
show(has_cycle(5, deps), has_cycle(3, [(0, 1), (1, 2), (2, 0)]))
show(components(7, [(0, 1), (1, 2), (3, 4)]))

Both versions print:

{"A":0,"B":3,"C":1,"D":4}
[0,1,2,3,4]
null
false true
[[0,1,2],[3,4],[5],[6]]

Dijkstra finds that B costs 3 (via C: 1 + 2, beating the direct edge of 4) and D costs 4 (via B). The dependency graph orders as 0, 1, 2, 3, 4. The three-node ring has no topological order, so the result is empty (None or null), and the cycle check agrees: the first graph has none, the second does. The seven vertices split into components 0-1-2, 3-4, and the isolated 5 and 6.

Common pitfalls

  • Skipping the stale-entry check: without if d > dist[u]: continue the algorithm still gives right answers but can reprocess vertices many times.
  • Using BFS on weighted edges: BFS counts edges, not cost. A path with fewer edges can be longer.
  • Confusing cycle detection rules: in a directed graph, seeing an already-visited vertex is not a cycle by itself; it must be on the current path (gray). In an undirected graph, the edge back to your parent is not a cycle.
  • Forgetting disconnected vertices: Kahn's algorithm and the cycle check must start from every vertex, not just one.
  • Assuming a unique topological order: tests that compare exact output fail when valid alternatives exist. Check the ordering property instead.
  • Unreachable vertices in Dijkstra: they never receive a distance. Decide whether to report infinity or omit them.

Practice

Number of connected components easy

Hint

Count how many fresh traversals you need to start.

Show solution

Build the adjacency list, loop over vertices, and start a DFS or BFS at each unseen one, incrementing a counter. O(V + E). Union-find offers the same answer with a different mechanism.

Course schedule (can all courses be finished?) medium

Hint

Prerequisites form a directed graph. When is a valid order impossible?

Show solution

Build edges from prerequisite to course and run Kahn's algorithm. All courses can be finished exactly when the output contains every course, meaning there is no cycle. For the ordering itself, return the output list. O(V + E).

Network delay time medium

Hint

You want the farthest of the shortest distances from the source.

Show solution

Run Dijkstra from the source. If any vertex is unreachable, return -1; otherwise the answer is the maximum value in the distance map, since a signal reaches everyone only when the slowest path arrives. O((V + E) log V).

Shortest path with the route, not just the cost hard

Hint

Remember who last improved each vertex.

Show solution

Keep a prev map. Whenever relaxing an edge improves dist[v], set prev[v] = u. After the algorithm, walk back from the target through prev until the source, then reverse the list. The extra space is O(V) and the time is unchanged.

Interview questions

  1. Why does Dijkstra fail with negative edges? It finalizes the closest vertex on the assumption nothing can improve it later, which only holds when weights are non-negative.
  2. What is the complexity of Dijkstra? O((V + E) log V) with a binary heap.
  3. How do you detect a cycle in a directed graph? DFS with a gray (on-path) state, or Kahn's algorithm leaving vertices unprocessed.
  4. What does a topological order exist for? Exactly the directed acyclic graphs. Cyclic graphs have none.
  5. BFS or Dijkstra? BFS when all edges cost the same, Dijkstra when weights differ and are non-negative.

Interviewers look for: naming the right algorithm from the problem statement (weights? directed? cycles?), stating preconditions like non-negative weights, and discussing the lazy-deletion trick with the priority queue.

Quick check

Every task in a build graph has been processed except tasks C and D, which each wait on the other. What does Kahn's algorithm report?

Finished this lesson?

Further resources

Related lessons