RevisionDojo

Question 1

Apply the Floyd–Warshall algorithm to detect whether there is a negative-weight cycle in the graph represented by the matrix

W = \begin{pmatrix} 0 & 4 & \infty & \infty \\ \infty & 0 & -2 & \infty \\ \infty & \infty & 0 & -1 \\ -5 & \infty & \infty & 0 \end{pmatrix}

and state your conclusion.

[4]

Question 2

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

[5]

Question 3

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

W = \begin{pmatrix} 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{pmatrix}

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

[5]

Question 4

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.

[5]

Question 5

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

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

$W = \begin{pmatrix} 0 & 2 & 8 \\ \infty & 0 & 1 \\ \infty & \infty & 0 \end{pmatrix}$

State the final distance matrix.

[3]

Question 6

Apply Dijkstra's algorithm to find shortest paths in a weighted graph.

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.

[6]

Question 7

Given the adjacency matrix of a directed graph with vertices $\{1, 2, 3, 4\}$ , using $\infty$ for no direct edge:

W = \begin{pmatrix} 0 & 3 & \infty & 7 \\ 8 & 0 & 2 & \infty \\ 5 & \infty & 0 & 1 \\ 2 & \infty & \infty & 0 \end{pmatrix}

Apply the Floyd–Warshall algorithm to compute the final distance matrix.

[6]

Question 8

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.

[5]

Question 9

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

Dijkstra Graph

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.

[5]

Question 10

Use the Floyd–Warshall algorithm on the directed graph with weight matrix

W = \begin{pmatrix} 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{pmatrix}

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.

[4]

Question 11

A weighted graph has vertices $\{A, B, C, D, E\}$ . The weight matrix $W$ for the graph is given by:

W = \begin{pmatrix} 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{pmatrix}

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.

[6]

Question 12

The following weighted undirected graph has vertices $A, B, C, D, E$ and edge weights: $AB = 4, AC = 2, BC = 1, BD = 5, CD = 8, CE = 10, DE = 2$ .

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

[6]

Question Type 4: Finding the shortest path in weighted graphs using Dijkstra's Algorithm Exercises