IB Mathematics Applications & Interpretation Question Type 4: Finding the Shortest Path in Weighted Graphs Using Dijkstra's Algorithm Exercises

Apply the Floyd–Warshall algorithm to detect whether there is a negative-weight cycle in the graph represented by the matrix $$W=\left(\begin{array}{cccc}0& 4& \infty & \infty \\ \infty & 0& -2& \infty \\ \infty & \infty & 0& -1\\ -5& \infty & \infty & 0\end{array}\right)$$ and state your conclusion.

Consider the directed graph with vertices $v_0,v_1,v_2,v_3$ and weighted edges $(v_0\to v_1:5)$, $(v_0\to v_2:3)$, $(v_1\to v_2:2)$, $(v_1\to v_3:6)$, $(v_2\to v_3:7)$. Use Dijkstra’s algorithm to determine the shortest path from $v_0$ to $v_3$.

Given a weighted directed graph with vertices 1–5 and weight matrix $W$:

$$W=\left(\begin{array}{ccccc}0& 3& \infty & 7& \infty \\ 3& 0& 1& \infty & 4\\ \infty & 1& 0& 2& 5\\ 7& \infty & 2& 0& 6\\ \infty & 4& 5& 6& 0\end{array}\right)$$

Use the Floyd–Warshall algorithm to determine the shortest distances between all pairs of vertices. Show the updates for each iteration $k=1,2,3,4,5$.

Consider the weighted directed graph with vertices $\{1,2,3,4\}$ and edges: $1\to 2$ with weight $3$, $2\to 3$ with weight $4$, $3\to 4$ with weight $-10$, and $4\to 2$ with weight $2$.

Use the Floyd–Warshall algorithm to determine whether this graph contains a negative cycle and compute the shortest-path distances if possible.

Apply the Floyd–Warshall algorithm to the following weight matrix $W$ for vertices $\{X,Y,Z\}$:

$$W=\left(\begin{array}{ccc}0& 2& 8\\ \infty & 0& 1\\ \infty & \infty & 0\end{array}\right)$$

State the final distance matrix.

Apply Dijkstra’s algorithm to a weighted undirected graph with vertices $\{1,2,3,4,5\}$ and the following edges:

• $\{1,2\}$ with weight 2
• $\{1,3\}$ with weight 4
• $\{2,3\}$ with weight 1
• $\{2,4\}$ with weight 7
• $\{3,5\}$ with weight 3
• $\{4,5\}$ with weight 1

Determine the order in which vertices are selected and the final shortest distances from vertex 1 to all other vertices.

Given the adjacency matrix of a directed graph with vertices $\{1,2,3,4\}$, using $\infty$ for no direct edge: $$W=\left(\begin{array}{cccc}0& 3& \infty & 7\\ 8& 0& 2& \infty \\ 5& \infty & 0& 1\\ 2& \infty & \infty & 0\end{array}\right)$$ Apply the Floyd–Warshall algorithm to compute the final distance matrix.

Using Dijkstra’s algorithm, find the shortest path from node $1$ to node $6$ in the weighted graph with the following edges:

$1-2:7,1-3:9,1-6:14,2-3:10,2-4:15,3-4:11,3-6:2,4-5:6,5-6:9$

State the shortest distance and the actual path.

Use Dijkstra’s algorithm, starting at node $S$, to find the shortest path to node $Z$ in the graph shown below.

Draw on this

The edges and their respective weights are: $S-A:6$, $S-B:3$, $A-C:5$, $B-A:2$, $B-C:3$, $C-D:4$, $D-Z:2$, $C-Z:6$.

Determine the shortest path and its total weight.

Use the Floyd–Warshall algorithm on the directed graph with weight matrix
$$W=\left(\begin{array}{ccccc}0& 1& \infty & 4& \infty \\ \infty & 0& 2& \infty & \infty \\ \infty & \infty & 0& 3& 5\\ \infty & \infty & \infty & 0& 1\\ \infty & \infty & \infty & \infty & 0\end{array}\right)$$ to find the length of the shortest path from vertex 1 to vertex 5. Show all iterations that change the shortest path estimate from vertex 1 to vertex 5.

A weighted graph has vertices $\{A,B,C,D,E\}$. The weight matrix $W$ for the graph is given by: $$W=\left(\begin{array}{ccccc}0& 7& 5& \infty & \infty \\ 7& 0& 3& 8& 6\\ 5& 3& 0& 4& \infty \\ \infty & 8& 4& 0& 2\\ \infty & 6& \infty & 2& 0\end{array}\right)$$ Use the Floyd–Warshall algorithm to find the shortest distance between vertex $B$ and vertex $E$. Show your working for each iteration of the intermediate vertices.

Apply Dijkstra’s algorithm to the graph to find the shortest path distances from vertex $A$ to all other vertices. Show your working clearly.