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 all
pairs of vertices by progressively considering each vertex as an
intermediate point.

At each step k, the algorithm
updates the distance matrix D (k) using the formula:

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

Assuming D (0) [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 ?

Question

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  all
pairs of vertices  by progressively considering each vertex as an
intermediate point.

At each step k, the algorithm
updates the distance matrix D (k)  using the formula:

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

Assuming D (0) [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 ?

Answer

The
algorithm correctly computes shortest paths between all pairs of vertices .

Answer

The
algorithm fails if the graph contains any negative-weight edges.

Answer

The
algorithm only works on undirected graphs.

Answer

The
algorithm computes shortest paths from a single source to all other vertices.

Crowdly

Let G=(V,E) be a directed graph with weighted edges (weights can be negative, b...

Want instant access to all verified answers on moodle.spit.ac.in?