[prev] 65 [next]

All-pair Shortest Path (APSP)

Given: weighted digraph G

Result: shortest paths between all pairs of vertices

  • dist[][] V×V-indexed matrix of cost of shortest path from vrow to vcol
  • path[][] V×V-indexed matrix of next node in shortest path from vrow to vcol
Example:

[Diagram:Pic/apsp.png]