Exercises — Shortest Paths

Chapter 10 · Fully solved exercises on Dijkstra, shortest-path LP, and optimality conditions

Exercise 1: Dijkstra Trace

Problem. Run Dijkstra’s algorithm from \(s\) on the following directed graph.

Nodes: \(s, a, b, c, t\) with positions \(s{=}(0,1)\), \(a{=}(2,2)\), \(b{=}(2,0)\), \(c{=}(4,1)\), \(t{=}(6,1)\).
Arcs: \(s{\to}a(2)\), \(s{\to}b(5)\), \(a{\to}c(3)\), \(a{\to}b(1)\), \(b{\to}c(2)\), \(b{\to}t(7)\), \(c{\to}t(1)\).

Find the shortest distances and predecessor tree from \(s\) to all nodes.

Solution.

Initialise: \(d = [s{:}0,\; a{:}\infty,\; b{:}\infty,\; c{:}\infty,\; t{:}\infty]\). Priority queue \(Q = \{(s,0)\}\).

Step	Extract	Update distances	\(Q\) after update
1	\(s\) (0)	\(d[a]=2\), \(d[b]=5\)	\(\{(a,2),(b,5)\}\)
2	\(a\) (2)	\(d[c]=\min(\infty,2{+}3)=5\), \(d[b]=\min(5,2{+}1)=3\)	\(\{(b,3),(c,5)\}\)
3	\(b\) (3)	\(d[c]=\min(5,3{+}2)=5\) (no impr.), \(d[t]=\min(\infty,3{+}7)=10\)	\(\{(c,5),(t,10)\}\)
4	\(c\) (5)	\(d[t]=\min(10,5{+}1)=6\)	\(\{(t,6)\}\)
5	\(t\) (6)	— (no outgoing arcs)	\(\emptyset\)

Final distances: \(d[s]=0\), \(d[a]=2\), \(d[b]=3\), \(d[c]=5\), \(d[t]=6\).

Predecessor tree: \(\text{pred}[a]=s\), \(\text{pred}[b]=a\), \(\text{pred}[c]=b\), \(\text{pred}[t]=c\).

Shortest \(s{\to}t\) path: \(s \xrightarrow{2} a \xrightarrow{1} b \xrightarrow{2} c \xrightarrow{1} t\), total cost \(= 2+1+2+1 = 6\). ✓

Exercise 2: Shortest Path as ILP

Problem. Formulate the shortest \(s\)-\(t\) path problem on the graph from Exercise 1 as an integer linear program. Verify the optimal solution.

Solution.

Introduce a binary variable \(x_e \in \{0,1\}\) for each arc \(e = (i,j)\), indicating whether arc \(e\) is used.

\[ \begin{aligned} & \text{minimise} && 2x_{sa} + 5x_{sb} + 3x_{ac} + x_{ab} + 2x_{bc} + 7x_{bt} + x_{ct} \\[4pt] & \text{subject to} && x_{sa} + x_{sb} = 1 & \text{(flow out of }s\text{)}\\ & && x_{ac} + x_{ab} - x_{sa} = 0 & \text{(conservation at }a\text{)}\\ & && x_{bc} + x_{bt} - x_{sb}-x_{ab}= 0 & \text{(conservation at }b\text{)}\\ & && x_{ct} - x_{ac} - x_{bc} = 0 & \text{(conservation at }c\text{)}\\ & && x_{ct} + x_{bt} = 1 & \text{(flow into }t\text{)}\\ & && x_e \in \{0,1\} & \forall e \end{aligned} \]

LP relaxation note. The constraint matrix above is the node-arc incidence matrix of a directed graph, which is totally unimodular (TU). Therefore the LP relaxation (\(x_e \in [0,1]\)) always yields an integer optimal solution — no branch-and-bound needed.

Optimal solution verification: set \(x_{sa}{=}x_{ab}{=}x_{bc}{=}x_{ct}{=}1\), all others \(0\).

Flow out of \(s\): \(1+0=1\) ✓
Conservation at \(a\): \(0+1-1=0\) ✓
Conservation at \(b\): \(1+0-0-1=0\) ✓
Conservation at \(c\): \(1-0-1=0\) ✓
Flow into \(t\): \(1+0=1\) ✓
Objective: \(2(1)+1(1)+2(1)+1(1) = 6 = d[t]\) ✓

Exercise 3: Is this the Shortest Path?

Problem. A student claims the shortest \(s\)-\(t\) path on the graph from Exercise 1 is \(s \to b \to t\) with cost \(12\). Is this correct? If not, identify the error and state the true shortest path.

Solution.

The student’s path:

\(s \to b\): cost \(= 5\) (direct arc).
\(b \to t\): cost \(= 7\).
Total: \(5 + 7 = 12\).

This path is feasible but not shortest. The error is that the student only considered the direct arc \(s \to b\) and ignored the cheaper route \(s \to a \to b\) (cost \(2+1=3\)). More importantly, they missed the path through \(c\):

\[s \xrightarrow{2} a \xrightarrow{1} b \xrightarrow{2} c \xrightarrow{1} t, \quad \text{total cost} = 6 < 12.\]

True shortest \(s \to t\) path: \(s \to a \to b \to c \to t\), cost \(= 6\).

Exercise 4: Optimality Conditions (Reduced Costs)

Problem. For a shortest-path tree rooted at \(s\) with distances \(d[v]\), define the reduced cost of arc \((i,j)\) as:

\[\bar{c}_{ij} = c_{ij} - d[j] + d[i].\]

The distances are optimal (i.e., form a valid shortest-path tree) if and only if \(\bar{c}_{ij} \geq 0\) for every arc \((i,j)\).

Using the graph from Exercise 1 and distances \(d{=}[s{:}0,\;a{:}2,\;b{:}3,\;c{:}5,\;t{:}6]\), verify the optimality conditions for all arcs.

Solution.

Arc \((i,j)\)	\(c_{ij}\)	\(d[i]\)	\(d[j]\)	\(\bar{c}_{ij} = c_{ij} - d[j] + d[i]\)	Status
\(s \to a\)	2	0	2	\(2 - 2 + 0 = 0\)	tight (on SP)
\(s \to b\)	5	0	3	\(5 - 3 + 0 = 2\)	slack
\(a \to c\)	3	2	5	\(3 - 5 + 2 = 0\)	tight
\(a \to b\)	1	2	3	\(1 - 3 + 2 = 0\)	tight (on SP)
\(b \to c\)	2	3	5	\(2 - 5 + 3 = 0\)	tight (on SP)
\(b \to t\)	7	3	6	\(7 - 6 + 3 = 4\)	slack
\(c \to t\)	1	5	6	\(1 - 6 + 5 = 0\)	tight (on SP)

All \(\bar{c}_{ij} \geq 0\) — the distances are optimal. Arcs with \(\bar{c}_{ij} = 0\) are candidates for the shortest-path tree (they are “tight”); arcs with \(\bar{c}_{ij} > 0\) cannot lie on any shortest path.

Exercise 5: Multiple Choice — Shortest Paths

Problem. Classify each statement as True or False and justify your answer.

Dijkstra’s algorithm works correctly with negative edge weights.
If all edge weights are equal, BFS finds shortest paths.
The shortest path between two nodes is always unique.
A shortest path cannot contain cycles (assuming non-negative weights).
Floyd-Warshall runs in \(O(n^3)\) and works for any graph without negative cycles.

Solution.

#	Verdict	Justification
(a)	FALSE	Dijkstra’s greedy “settle the closest node” step is invalid when a negative arc could later decrease an already-settled distance. Use Bellman-Ford for graphs with negative weights.
(b)	TRUE	BFS finds paths with the minimum number of hops. When all weights equal 1, hop count equals path cost, so BFS gives optimal shortest paths.
(c)	FALSE	Multiple paths can share the same minimum cost. Example: two parallel arcs of equal weight both yield shortest paths.
(d)	TRUE	With non-negative weights any cycle has cost \(\geq 0\). Removing a cycle from a path yields a walk of equal or lower cost, and since it is also a path (no repeated nodes), it is at least as short. Hence shortest paths can always be taken to be simple (cycle-free).
(e)	TRUE	Floyd-Warshall uses three nested loops over \(n\) nodes: \(O(n^3)\). It handles negative-weight arcs and detects negative cycles (a negative diagonal entry after termination).