Graph / Parallel algorithms / interactive lesson
Distribute Dijkstra's shortest-path computation across workers. Compare local tentative minima, reduce them to a globally safe vertex, relax outgoing edges concurrently, and synchronize at explicit barriers.
Worker P0
A Blocal min - / INF
relax 0 edges / update 0
Worker P1
C Dlocal min - / INF
relax 0 edges / update 0
Worker P2
E Flocal min - / INF
relax 0 edges / update 0
Parallel round timeline
Partition 6 vertices across 3 workers
About the algorithm
Parallel Dijkstra preserves the greedy rule of the sequential algorithm while distributing useful work among processors. Workers scan local vertices simultaneously, reduce their local minima to one globally safe choice, then relax edges from that selected vertex in parallel before synchronizing for the next round.
Large graphs may contain millions of vertices and edges. Partitioning vertices lets processors scan local queues and apply independent relaxation updates concurrently. The speedup is real but limited by global coordination: the next settled vertex still depends on a minimum reduction.
Give each worker a block of vertices. In every round, workers find local minimum tentative distances. A reduction selects the global minimum, which becomes final. Its outgoing neighbors are relaxed by their owning workers, followed by a barrier that exposes all updates to the next round.
Performance depends on partition quality, communication latency, graph density, and available processors. Shared-memory versions may use concurrent priority queues or atomic minima. Distributed-memory systems often exchange frontier updates and spend careful effort reducing synchronization overhead.
Code companion
Connect each visual decision to an implementation pattern.
partition vertices among p workers
distance[source] = 0
while reachable unsettled vertices remain:
in parallel for each worker:
localCandidate[worker] = minimum unsettled local vertex
current = globalMinReduction(localCandidate)
settle current
broadcast current
in parallel for each worker:
for each neighbor of current owned by worker:
distance[neighbor] = min(
distance[neighbor],
distance[current] + weight(current, neighbor))
barrier()
return distance, predecessor