[prev] [index] [next]

Single-source Shortest Path

Given: weighted digraph G, source vertex s

Result: shortest paths from s to all other vertices

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

[Diagram:Pics/wgraphs/sssp.png]