[prev] 166 [next]

Floyd's Algorithm (cont)

Why Floyd's algorithm is correct:

A shortest path from s to t using only nodes from {0,…,i} is the shorter of

  • a shortest path from s to t using only nodes from {0,…,i-1}
  • a shortest path from s to i using only nodes from {0,…,i-1}
    plus a shortest path from i to t using only nodes from {0,…,i-1}

[Diagram:Pic/relaxation-floyd.png]

Also known as Floyd-Warshall algorithm   (can you see why?)