RevisionDojo

Question 1

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)}$ .

[6]

Question 2

This question assesses the student's understanding of the Floyd–Warshall algorithm, its implementation via nested loops, its computational efficiency (time and space complexity), and its limitations regarding graph properties.

Consider a network with 6 nodes. Describe the general process of the Floyd–Warshall algorithm as the iteration index $k$ increases from 1 to 6. In your response:

Include the specific update rule used in each iteration.
Explain the resulting time complexity of the algorithm.
State the space complexity of the algorithm.
Identify a condition regarding cycles in the network under which the algorithm would fail to provide a correct result.

[6]

Question 3

Apply the Floyd–Warshall algorithm to find the shortest-path distance matrix for the following $5 \times 5$ matrix, and then reconstruct the shortest path from vertex 1 to vertex 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}

[6]

Question 4

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 the Floyd–Warshall algorithm to find the matrix of shortest distances.

[5]

Question 5

The Floyd–Warshall algorithm for finding shortest paths in a weighted graph.

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 the Floyd–Warshall algorithm, what is the shortest distance from node 3 to node 2? Show the key update steps.

[5]

Question 6

A graph on vertices $\{A, B, C, D, E\}$ has negative edge weights but no negative cycles. Its initial distance matrix $D^{(0)}$ is given by

$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 the Floyd–Warshall algorithm to compute the final matrix of all-pairs shortest path distances. Show the intermediate matrices $D^{(2)}$ and $D^{(4)}$ to demonstrate your process.

[6]

Question 7

The graph's initial distance matrix $D^{(0)}$ is provided for vertices $V = \{1, 2, 3, 4\}$ . The Floyd–Warshall algorithm is used to find the shortest paths between all pairs of vertices. The predecessor matrix $\Pi$ is defined such that $\Pi_{ij}$ is the predecessor of vertex $j$ on the shortest path from vertex $i$ .

Given the following initial distance matrix $D^{(0)}$ for a weighted directed graph on vertices $\{1, 2, 3, 4\}$ , compute the final distance matrix $D^{(4)}$ and the corresponding predecessor matrix $\Pi^{(4)}$ by tracing the Floyd–Warshall algorithm.

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

[6]

Question 8

The question asks for the application of the Floyd–Warshall algorithm to an adjacency matrix of a weighted directed graph to detect the presence of negative-weight cycles.

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}

[5]

Question 9

The following matrix represents the initial distances between five vertices, $P, Q, R, S$ , and $T$ , in a weighted directed graph.

Using the Floyd–Warshall algorithm, find the shortest‐path distance from vertex $P$ to vertex $Q$ in the graph represented by the initial distance matrix $D^{(0)}$ . Specify the shortest path.

$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}$

[4]

Question 10

Construct the transitive closure matrix of the graph represented by the following weight matrix:

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

Compare this transitive closure to the reachability matrix derived from the Floyd–Warshall algorithm.

[5]

Question 11

A graph has 4 vertices and its edge weights are given by the following initial distance matrix $D^{(0)}$ , where $\infty$ denotes no direct edge between vertices:

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 state the final distance matrix $D^{(4)}$ .

[4]

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