Shortest-Path Basics

1Introduction

This lecture formulates shortest-path problems that minimize either the number of edges or the sum of edge weights. It then explains the applicability conditions for BFS, Dijkstra's algorithm, and methods that permit negative edges.

The lecture assumes the definitions of vertices, edges, walks, and paths, together with the layered structure of BFS.

2Graphs and routes

Let $$G=(V,E)$$G=(V,E) be a finite graph. An edge $$\{u,v\}$$\{u,v\} of an undirected graph has no orientation, whereas a directed edge $$(u,v)$$(u,v) permits movement only from $$u$$u to $$v$$v.

An $$s$$s-to-$$t$$t walk is a vertex sequence $$v_0=s,v_1,\dots ,v_k=t$$v_0=s,v_1,\ldots,v_k=t in which an edge of $$E$$E joins every pair of consecutive vertices. In a directed graph, each edge orientation must also agree with the sequence. A walk with no repeated vertex is a path. Its number of edges is $$k$$k.

An edge-weight function is a function $$w:E\to \mathbb{R}$$w:E\to\mathbb{R} that assigns a real number to each edge. The cost of a walk $$P=(v_0,\dots ,v_k)$$P=(v_0,\ldots,v_k) is

For an undirected edge, $$w(v_{i-1},v_i)$$w(v_{i-1},v_i) denotes the weight of the undirected edge joining those two vertices. Minimizing the number of edges is equivalent to assigning weight $$1$$1 to every edge.

3Distance and unreachability

Define the distance from $$s$$s to $$t$$t as the infimum of the costs of all $$s$$s-to-$$t$$t walks:

If $$t$$t is unreachable from $$s$$s, the candidate set is empty, and we define $$\delta (s,t)=+\mathrm{\infty }$$\delta(s,t)=+\infty.

A closed walk is a walk whose first and last vertices coincide. A cycle is a closed walk with no repeated vertices other than its coincident endpoints. In a directed graph, every negative closed walk contains at least one negative cycle in its decomposition.

Suppose a negative cycle is reachable from $$s$$s and $$t$$t is reachable from that cycle. Repeating the cycle arbitrarily many times gives $$\delta (s,t)=-\mathrm{\infty }$$\delta(s,t)=-\infty, and no walk attains a minimum cost. In an undirected graph, traversing a negative edge in both directions forms a negative closed walk. Thus the distance is $$-\mathrm{\infty }$$-\infty whenever such an edge can occur on an $$s$$s-to-$$t$$t route.

Now suppose that no relevant negative cycle exists and that $$t$$t is reachable. If an arbitrary $$s$$s-to-$$t$$t walk repeats a vertex, the intervening closed subwalk has nonnegative cost and can be removed without increasing the cost. Repeating this operation produces a path. A finite graph has only finitely many $$s$$s-to-$$t$$t paths, so one of them attains the minimum cost. Such a path is called a shortest path from $$s$$s to $$t$$t.

4Choosing a method from the weights

4.1Equal edge weights

If all edge weights equal the same positive constant $$c>0$$c>0, the cost is $$c$$c times the number of edges. Thus minimizing cost is equivalent to minimizing the number of edges. BFS processes vertices in nondecreasing order of their edge counts from the source, so it computes the shortest distance to every reachable vertex. An unweighted graph is interpreted as the case $$c=1$$c=1.

4.2Nonnegative edge weights

If $$w\left(e\right)\ge 0$$w(e)\geq0 for every edge, Dijkstra's algorithm applies. It selects an unsettled vertex with minimum tentative distance and uses candidate routes through that vertex to update the tentative distances of adjacent vertices. Nonnegativity ensures that no later route can decrease a settled distance.

4.3Negative edges

A negative edge is an edge $$e$$e with $$w\left(e\right)<0$$w(e)<0. If even one negative edge exists, the justification for settling vertices solely by tentative distance in Dijkstra's algorithm no longer holds. A negative edge alone, however, does not imply that a shortest path fails to exist. If no relevant negative cycle exists, a method that permits negative edges, such as the Bellman--Ford algorithm, can be used.

5Optimal substructure

Let $$P=(v_0,\dots ,v_k)$$P=(v_0,\ldots,v_k) be a shortest path from $$v_0$$v_0 to $$v_k$$v_k. For every $$0\le i<j\le k$$0\leq i<j\leq k, the subpath $$P[i:j]=(v_i,\dots ,v_j)$$P[i:j]=(v_i,\ldots,v_j) is also a shortest path from $$v_i$$v_i to $$v_j$$v_j. This property is called the optimal substructure of shortest paths.

Indeed, suppose that a walk $$Q$$Q from $$v_i$$v_i to $$v_j$$v_j had lower cost than $$P[i:j]$$P[i:j]. Replacing that portion of $$P$$P with $$Q$$Q would construct a walk from $$v_0$$v_0 to $$v_k$$v_k with lower cost than $$P$$P, contradicting the optimality of $$P$$P. The claim therefore holds. This property underlies shortest-path algorithms that combine optimal values of subproblems through relaxation.

6Summary

• A shortest-path problem must specify whether the graph is directed or undirected and distinguish walks from paths.
• The distance is $$+\mathrm{\infty }$$+\infty when the target is unreachable and $$-\mathrm{\infty }$$-\infty when a relevant negative cycle exists.
• BFS applies to equal weights, and Dijkstra's algorithm applies to nonnegative weights. Negative edges require a different method.
• Every subpath of a shortest path is itself a shortest path between its endpoints.