graph - shortest path algorithm cost calculation -

graph - shortest path algorithm cost calculation -

so question goes this: give directed graph g=(v,e) , weight function wt: e->r+. given 2 distinguished nodes s,t ∈ v write algorithm marks every node v such v lies on shortest path s t. is, introduce boolean field on each node v. algorithm should found post condition: ∀ v ∈ v : v.on ≡ ( ∃ p: shpath(p,s,t) ∩ along(v,p)) define shpath(p,s,t) = path(p,s,t) ∩ wt(p) = δ(s,t), , along(v,p) = (v = hd(p) ∪ along(v,tl(p))). here hd, tl denote head , tail of sequence. along(v,λ) = false, λ empty sequence. prove algorithm terminates in time o(|v|^3), above postcondition true

i've been trying figure out, there somethings don't understand, assuming there multiple shortest paths? , should find shortest path see nodes belong path? or should find these nodes while we're in process of finding shortest path? , how should prove algorithm terminate in time o(|v|^3), please help...

are assuming there multiple shortest paths?

there may many shortest paths, yes. consider graph like

* * * * / \ / \ / \ / \ s * * * t \ / \ / \ / \ / * * * *

where each border has length 1. there 16 shortest paths s t.

and should find shortest path see nodes belong path?

if seek on graph above, you'll fail mark 4 nodes.

or should find these nodes while we're in process of finding shortest path?

perhaps, perhaps not. there several right algorithms.

and how should prove algorithm terminate in time o(|v|^3)

you should worry proving correctness first.

algorithm graph graph-theory dijkstra shortest-path