Reference no: EM131575219

Question: Give a big-O estimate of the number of operations (comparisons and additions) used by Floyd's algorithm to determine the shortest distance between every pair of vertices in a weighted simple graph with n vertices.

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}