[prev] 58 [next]

Single-source Shortest Path (SSSP)

Given: weighted digraph G, source vertex s

Result: shortest paths from s to all other vertices

  • dist[] V-indexed array of cost of shortest path from s
  • pred[] V-indexed array of predecessor in shortest path from s
Example:

[Diagram:Pic/sssp.png]