IB Mathematics Applications & Interpretation Question Type 5: Using Floyd-warshall for All Pairs Shortest Path Exercises

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

$$D^{(0)}=\left(\begin{array}{ccc}0& 3& \infty \\ 2& 0& 5\\ \infty & 1& 0\end{array}\right)$$

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

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.

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)}=\left(\begin{array}{ccccc}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{array}\right)$$

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

$$D^{(0)}=\left(\begin{array}{cccc}0& 4& \infty & 10\\ \infty & 0& 3& \infty \\ \infty & \infty & 0& 1\\ \infty & \infty & \infty & 0\end{array}\right)$$

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

A graph has adjacency matrix

$$D^{(0)}=\left(\begin{array}{cccc}0& 5& \infty & 10\\ \infty & 0& 3& \infty \\ 4& \infty & 0& 1\\ \infty & \infty & \infty & 0\end{array}\right)$$

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

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)}=\left(\begin{array}{ccccc}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{array}\right)$$

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.

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)}=\left(\begin{array}{cccc}0& 8& \infty & 1\\ 6& 0& 4& \infty \\ \infty & 2& 0& 3\\ \infty & \infty & \infty & 0\end{array}\right)$$

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

$$D^{(0)}=\left(\begin{array}{ccc}0& 1& \infty \\ \infty & 0& -2\\ 4& \infty & 0\end{array}\right)$$

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)}=\left(\begin{array}{ccccc}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{array}\right)$$

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

$$D^{(0)}=\left(\begin{array}{cccc}0& 1& \infty & \infty \\ \infty & 0& 1& \infty \\ \infty & \infty & 0& 1\\ 1& \infty & \infty & 0\end{array}\right)$$

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

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)}=\left(\begin{array}{cccc}0& 1& \infty & 5\\ 2& 0& 3& \infty \\ \infty & \infty & 0& 2\\ \infty & \infty & \infty & 0\end{array}\right)$$

Perform the Floyd–Warshall algorithm and state the final distance matrix $D^{(4)}$.