Algorithm
G = (V, E) d(i) – the distance of vertex i (i∈V) from source vertex A; it’s the sum of arcs in a possible path from vertex A to vertex i. Note that d(A)=0; P(i) – the predecessor of vertex I on the same path. Z – the destination vertex
Step 1.
Start with d(A)=0, d(i) = l (Ai), if i∈ΓA; = ∞, otherwise (∞ is a large number defined below); Γi ≡ set of neighbor vertices of vertex i, l(ij) = length of arc from vertex i to vertex j. Assign S = V-{A}, where V is the set of vertices in the given graph. Assign P(i) = A, ∀i∈S.Step 2.
a) Find j∈S such that d(j) = min d(i), i∈S. b) Set S = S – {j}. c) If j = Z (the destination vertex), END; otherwise go to Step 3.Step 3.
∀i∈Γj, if d(j)+l(ij)Read more about this topic: Edge Disjoint Shortest Pair Algorithm
Related Phrases
Related Words