Properties of shortest path 7 x Subpaths of shortest paths are shortest paths <S,X, X s→pX <sx X.U.V」 X→→pV=<X,u> u-p V
8 9 u v 1 5 7 x y 2 0 10 5 7 9 2 3 4 6 s Properties of Shortest Path • Subpaths of shortest paths are shortest paths. • s →p v = <s, x, u, v> • s →p u = <s, x, u> • s →p x = <s, x> • x →p v = <x, u, v> • x →p v = <x, u> • u →p v = <u, v>
Properties of shortest path 7 Corollary: Shortest paths can be grown from shortest paths The length of shortest path s→Ppu→V S(s,v)=6(s,u)+w(u,v). V<u,p>∈Eδ(,v)≤δ(s,u)+w(u,y)
Properties of Shortest Path 8 9 u v 1 5 7 x y 2 0 10 5 7 9 2 3 4 6 s Corollary: Shortest paths can be grown from shortest paths. • The length of shortest path s → p u → v is δ (s,v) = δ (s,u ) + w (u,v). • ∀ <u,v> ∈ E δ (s,v) ≤ δ (s,u) + w (u,v )