RevisionDojo

Question 1

Skill question

Consider the directed graph with vertices v₀, v₁, v₂, v₃ and weighted edges (v₀→v₁:5), (v₀→v₂:3), (v₁→v₂:2), (v₁→v₃:6), (v₂→v₃:7). Use Dijkstra’s algorithm to determine the shortest path from v₀ to v₃.

Question 2

Skill question

Using Dijkstra’s algorithm, find the shortest path from node 1 to node 6 in the weighted graph with 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. Also give the actual path.

Question 3

Skill question

Apply Dijkstra’s algorithm to the following weighted undirected graph with vertices A, B, C, D, E and edge weights: AB = 4, AC = 2, BC = 1, BD = 5, CD = 8, CE = 10, DE = 2. Find the shortest path distances from A to all other vertices.

Question 4

Skill question

In the graph below, run Dijkstra’s algorithm starting at node S to find the shortest path to node Z. Edges: S–A:6, S–B:3, A–C:5, B–A:2, B–C:3, C–D:4, D–Z:2, C–Z:6. What is the shortest path and its total weight?

Question 5

Skill question

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

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

and report the final distance matrix.

Question 6

Skill question

Apply Dijkstra’s algorithm to this weighted undirected graph with vertices 1–5 and edges: 1–2:2, 1–3:4, 2–3:1, 2–4:7, 3–5:3, 4–5:1. Determine the order in which vertices are selected and their final shortest distances from 1.

Question 7

Skill question

Given the adjacency matrix of a directed graph with vertices {1,2,3,4}, using ∞ 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.

Question 8

Skill question

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.

Question 9

Skill question

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

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 compute the shortest distances between all pairs of vertices.

Question 10

Skill question

Given a graph with vertices {A,B,C,D,E} and weight matrix:

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 B and E.

Question 11

Skill question

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.

Question 12

Skill question

Consider the weighted directed graph with vertices {1,2,3,4} and edges: 1→2:3, 2→3:4, 3→4:-10, 4→2:2. Use the Floyd–Warshall algorithm to determine whether this graph contains a negative cycle and compute the shortest-path distances if possible.

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