Reference no: EM131575215

Question: Show that Dijkstra's algorithm may not work if edges can have negative weights.

Floyd's algorithm, displayed as Algorithm 2, can be used to find the length of a shortest path between all pairs of vertices in a weighted connected simple graph. However, this algorithm cannot be used to construct shortest paths. (We assign an infinite weight to any pair of vertices not connected by an edge in the graph).

ALGORITHM 2 Floyd's Algorithm.

procedure Floyd(G: weighted simple graph)

{G has vertices v₁, v₂........... v_n and weights w(v_i, v_j)

with w(v_i, v_j) = ∞ if {v_i, v_j} is not an edge}

for i := 1 to n

for j := 1 to n

d(v_i, v_j):= w(v_i, v_j)

for i := 1 to n

for j := 1 to n

for k := 1 to n

if d(vj, v_i) + d(vi, vk) < d(v_j, v_k)

then d(v_j, v_k) := d(vj, v_i) + d(vi, vk)

return [d(v_i, v_j)] {d(v_i, v_j) is the length of a shortest path between vi and vj for 1 ≤ i ≤ n, 1 ≤ j ≤ n}