Let G=(V,E) be a directed graph

with weighted edges (weights can be negative, but no negative-weight cycles).

You are given an algorithm that computes the shortest path distances between

At each step k, the algorithm

updates the distance matrix D

D^(k)[i][j]=min(D(k−1)[i][j],D^(k−1)[i][k]+D^(k−1)[k][j])

Assuming D⁽⁰⁾

[i][j] is

initialized as:

1.0 if i=j

2.weight of edge (i,j) if it

exists

3. ∞ otherwise

Which of the following is TRUE?