RevisionDojo

Question 1

Skill question

Apply the Floyd–Warshall algorithm to the following adjacency matrix of a directed graph with vertices 1, 2, 3:

D^{(0)} = \begin{pmatrix} 0 & 3 & \infty \\ 2 & 0 & 5 \\ \infty & 1 & 0 \end{pmatrix}

Compute the all‐pairs shortest‐path distance matrix $D^{(3)}$ .

Question 2

Skill question

A graph has adjacency matrix

$D^{(0)}=\begin{pmatrix}0&5&\infty&10\\\infty&0&3&\infty\\4&\infty&0&1\\\infty&\infty&\infty&0\end{pmatrix}$

After running Floyd–Warshall, what is the distance from 3 to 2? Show the key update steps.

Question 3

Skill question

The graph below has 4 vertices and edge weights (∞ means no direct edge):

D^{(0)} = \begin{pmatrix} 0 & 1 & \infty & 5\\ 2 & 0 & 3 & \infty\\ \infty & \infty & 0 & 2\\ \infty & \infty & \infty & 0 \end{pmatrix}

Perform the Floyd–Warshall algorithm and give $D^{(4)}$ .

Question 4

Skill question

Using Floyd–Warshall, find the shortest‐path distance from vertex P to Q in this graph of 5 nodes given by

$D^{(0)}=\begin{pmatrix}0&2&\infty&1&\infty\\\infty&0&3&2&\infty\\\infty&\infty&0&\infty&4\\1&\infty&2&0&5\\\infty&\infty&\infty&\infty&0\end{pmatrix}$

and specify the path.

Question 5

Skill question

Given the weighted directed graph with vertices A, B, C, D and adjacency matrix

D^{(0)} = \begin{pmatrix} 0 & 4 & \infty & 10\\ \infty & 0 & 3 & \infty\\ \infty & \infty & 0 & 1\\ \infty & \infty & \infty & 0 \end{pmatrix}

use Floyd–Warshall to find the matrix of shortest distances.

Question 6

Skill question

Apply the Floyd–Warshall algorithm to detect whether the following graph has a negative‐weight cycle. The adjacency matrix is

D^{(0)} = \begin{pmatrix} 0 & 1 & \infty\\ \infty & 0 & -2\\ 4 & \infty & 0 \end{pmatrix}

Question 7

Skill question

Construct the transitive closure matrix of the graph

$D^{(0)}=\begin{pmatrix}0&1&\infty&\infty\\\infty&0&1&\infty\\\infty&\infty&0&1\\1&\infty&\infty&0\end{pmatrix}$

and compare it to the reachability after Floyd–Warshall.

Question 8

Skill question

In a network of 6 nodes, the distance matrix at iteration $k=0$ is given. Describe generally how Floyd–Warshall would process $k$ from 1 to 6, and explain the time complexity.

Question 9

Skill question

Given the following weighted directed graph on vertices {1,2,3,4}, compute the predecessor matrix $\Pi^{(4)}$ alongside the distance matrix by running Floyd–Warshall on

D^{(0)}=\begin{pmatrix}0&8&\infty&1\\6&0&4&\infty\\\infty&2&0&3\\\infty&\infty&\infty&0\end{pmatrix}.

Question 10

Skill question

Apply Floyd–Warshall to find the shortest‐path distance matrix for the following 5×5 matrix, and then reconstruct the shortest path from vertex 1 to 5:

D^{(0)}=\begin{pmatrix} 0&2&\infty&1&\infty\\ \infty&0&3&2&\infty\\ \infty&\infty&0&\infty&4\\ 1&\infty&2&0&5\\ \infty&\infty&\infty&\infty&0 \end{pmatrix}

Question 11

Skill question

A graph on vertices {A,B,C,D,E} has negative edge weights but no negative cycles. Its initial matrix is

$D^{(0)}=\begin{pmatrix}0&3&8&\infty&-4\\\infty&0&\infty&1&7\\\infty&4&0&\infty&\infty\\2&\infty&-5&0&\infty\\\infty&\infty&\infty&6&0\end{pmatrix}$

Use Floyd–Warshall to compute all‐pairs distances.

Question Type 5: Using Floyd-Warshall for all pairs shortest path Exercises