The Central Idea
A shortest-path problem asks:
\[ \boxed{\text{Which route has the smallest total weight?}} \]The answer depends on the edge weights, not merely on the number of edges used.
Path Weight
Suppose a path
\[ P=v_0,v_1,\ldots,v_k \]uses edges with weights
\[ w_1,w_2,\ldots,w_k. \]For additive weights, the total path weight is
\[ \boxed{w(P)=w_1+w_2+\cdots+w_k}. \]Shortest Path between Two Vertices
A shortest path from \(u\) to \(v\) is a \(u\)-\(v\) path whose total weight is minimum among all \(u\)-\(v\) paths.
If \(\mathcal{P}(u,v)\) is the set of all \(u\)-\(v\) paths, then
\[ \boxed{ d(u,v)=\min_{P\in\mathcal{P}(u,v)}w(P) }. \]The quantity \(d(u,v)\) is called the weighted distance from \(u\) to \(v\).
A First Weighted Example
Consider the weighted graph with edges
\[ w(A,B)=4,\qquad w(A,C)=2,\qquad w(B,C)=1,\qquad w(B,D)=5,\qquad w(C,D)=8,\qquad w(C,E)=10,\qquad w(D,E)=2. \]We will compare routes from \(A\) to \(E\).
The Example as a Picture
Comparing Candidate Routes
One route from \(A\) to \(E\) is
\[ A,C,E, \]with total weight
\[ 2+10=12. \]Another route is
\[ A,B,D,E, \]with total weight
\[ 4+5+2=11. \]A Better Route
Consider
\[ A,C,B,D,E. \]Its weight is
\[ 2+1+5+2=10. \]This is smaller than both \(12\) and \(11\).
Shortest Does Not Mean Fewest Edges
The route
\[ A,C,E \]uses only two edges but has weight \(12\).
The route
\[ A,C,B,D,E \]uses four edges but has weight \(10\).
Therefore,
\[ \boxed{\text{fewest edges}\ne\text{minimum total weight}}. \]Unweighted Graph Distance
In an unweighted graph, every edge may be treated as having weight \(1\).
Then the shortest-path distance becomes the minimum number of edges between two vertices.
Thus unweighted shortest paths are a special case of weighted shortest paths.
Directed Shortest Paths
In a directed graph, a path must follow arrow directions.
Therefore
\[ d(u,v) \]may differ from
\[ d(v,u). \]One direction may even be reachable while the reverse direction is not.
Unreachable Vertices
If no path exists from \(u\) to \(v\), then the distance is commonly represented as
\[ \boxed{d(u,v)=\infty}. \]The symbol indicates that no finite route is available.
Single-Source Shortest Paths
A single-source shortest-path problem asks for the shortest paths from one chosen source vertex \(s\) to every other reachable vertex.
Dijkstra's algorithm is a standard method for this problem when all edge weights are nonnegative.
Dijkstra's Algorithm
Dijkstra's algorithm gradually finalizes the shortest known distance from a source to each vertex.
It relies on the assumption
\[ \boxed{w(e)\ge0\text{ for every edge }e}. \]Tentative Distances
At the start, assign the source distance
\[ d(s)=0 \]and every other vertex
\[ d(v)=\infty. \]These values are tentative until they are finalized.
Relaxing an Edge
Suppose we know a tentative distance to \(u\), and there is an edge from \(u\) to \(v\) of weight \(w(u,v)\).
We compare the current distance to \(v\) with
\[ d(u)+w(u,v). \]If the new route is better, update:
\[ \boxed{ d(v)\leftarrow \min\bigl(d(v),d(u)+w(u,v)\bigr) }. \]This update is called relaxation.
Selecting the Next Vertex
Among all unfinalized vertices, choose one with the smallest tentative distance.
Finalize that distance, then relax the outgoing or incident edges from that vertex.
Continue until all reachable vertices are finalized or until the target vertex has been finalized.
Why Nonnegative Weights Matter
Once Dijkstra's algorithm finalizes a vertex, it assumes no later route can improve that distance.
Nonnegative edge weights guarantee this property.
Negative edges can violate it.
Dijkstra Example: Initialization
Use the earlier graph with source \(A\).
Initially,
\[ d(A)=0, \]and
\[ d(B)=d(C)=d(D)=d(E)=\infty. \]Dijkstra Example: From \(A\)
Relax the edges from \(A\):
\[ d(B)=4, \] \[ d(C)=2. \]The smallest unfinalized distance is now
\[ d(C)=2. \]Finalize \(C\).
Dijkstra Example: From \(C\)
Through \(C\), the route to \(B\) has weight
\[ 2+1=3, \]improving the previous value \(4\):
\[ d(B)=3. \]We also obtain
\[ d(D)=2+8=10 \]and
\[ d(E)=2+10=12. \]Dijkstra Example: From \(B\)
The next smallest unfinalized distance is
\[ d(B)=3. \]Relaxing the edge \(B-D\) gives
\[ 3+5=8. \]This improves
\[ d(D)=10 \]to
\[ d(D)=8. \]Dijkstra Example: From \(D\)
Finalize \(D\) at distance
\[ 8. \]Relaxing \(D-E\) gives
\[ 8+2=10. \]This improves
\[ d(E)=12 \]to
\[ d(E)=10. \]Dijkstra Example: Final Distances
The shortest distances from \(A\) are
\[ d(A)=0, \] \[ d(C)=2, \] \[ d(B)=3, \] \[ d(D)=8, \] \[ d(E)=10. \]Therefore,
\[ \boxed{d(A,E)=10}. \]Tracking Predecessors
Distance values tell us how short the best route is, but not automatically which route achieved it.
Whenever a relaxation improves \(d(v)\), record the vertex that produced the improvement as the predecessor of \(v\).
Reconstructing the Shortest Path
In the example, the predecessor chain is
\[ E\leftarrow D\leftarrow B\leftarrow C\leftarrow A. \]Reversing this chain gives
\[ \boxed{A,C,B,D,E}. \]Its weight is
\[ 2+1+5+2=10. \]Shortest-Path Tree
If we record one predecessor for every reachable non-source vertex, the selected predecessor edges form a shortest-path tree rooted at the source.
The unique tree path from the source to each vertex is a shortest path in the original graph.
Shortest-Path Tree versus Minimum Spanning Tree
These structures solve different optimization problems.
A shortest-path tree minimizes source-to-vertex distances.
A minimum spanning tree minimizes the total weight of all selected tree edges.
They need not be the same tree.
Multiple Shortest Paths
Two or more different paths may have the same minimum total weight.
In that case the shortest path is not unique.
The distance
\[ d(u,v) \]is still uniquely defined as a number, even if several routes attain it.
Example: A Tie
Suppose
\[ A-B-D \]has weight
\[ 3+4=7, \]and
\[ A-C-D \]has weight
\[ 2+5=7. \]Then both routes are shortest paths from \(A\) to \(D\).
Zero-Weight Edges
Dijkstra's algorithm permits zero-weight edges because
\[ 0\ge0. \]A zero-weight edge contributes nothing to the route cost but still counts as an actual edge.
Negative Edge Weights
Dijkstra's algorithm should not be used when negative edge weights are present.
Other algorithms, such as Bellman-Ford, are designed for graphs that may contain negative edges.
Negative Cycles
If a reachable directed cycle has negative total weight, then repeatedly traversing that cycle can reduce the route weight without bound.
In such a case, a finite shortest path to some vertices may not exist.
Shortest Paths in Unweighted Graphs
When every edge has equal weight, breadth-first search can find shortest paths by exploring vertices in increasing numbers of edges from the source.
The first time a vertex is reached gives its minimum edge-count distance.
Applications of Shortest Paths
Shortest-path models appear in:
- road navigation;
- airline routing;
- packet routing;
- robot motion planning;
- supply-chain logistics;
- workflow optimization;
- game and state-space search;
- social-network distance;
- dependency analysis.
What the Weight Represents Matters
A shortest path minimizes whatever quantity the edge weights encode.
If weights measure time, the result is a minimum-time route.
If weights measure cost, the result is a minimum-cost route.
If weights measure distance, the result is a minimum-distance route.
One Network Can Have Several Weight Systems
The same road network might use:
- distance weights;
- travel-time weights;
- toll-cost weights;
- fuel-use weights.
Each weight system can produce a different shortest route.
Common Error: Choosing the Fewest Edges
In a weighted graph, a path with fewer edges may have a larger total weight.
Always compare the sum of the edge weights.
Common Error: Choosing the Smallest Next Edge Greedily
Simply taking the smallest available edge at each step does not guarantee a globally shortest path.
Shortest-path algorithms compare cumulative route costs, not only the next local edge.
Common Error: Forgetting Direction
In a directed graph, an edge
\[ u\to v \]cannot be used in reverse unless
\[ v\to u \]is also present.
Common Error: Finalizing Too Early
In Dijkstra's algorithm, a vertex is finalized only when it has the smallest tentative distance among all unfinalized vertices.
A merely discovered route is not automatically final.
Common Error: Using Dijkstra with Negative Weights
Dijkstra's correctness depends on nonnegative edge weights.
Negative weights require a different method.
Common Error: Reporting Only the Distance
A problem may ask for the actual shortest path, not merely its weight.
Record predecessors so the route can be reconstructed.
A Reliable Procedure for Shortest-Path Problems
- Identify the source and target vertices.
- Confirm what the edge weights represent.
- Check whether the graph is directed or undirected.
- Check whether all weights are nonnegative.
- Use Dijkstra's algorithm when its assumptions apply.
- Relax edges using cumulative path weights.
- Track predecessors whenever a distance improves.
- Stop when the target is finalized, or continue for all-source distances.
- Reconstruct the route from the predecessor chain.
Dijkstra's Algorithm: Compact Form
- Set \(d(s)=0\) and \(d(v)=\infty\) for all \(v\ne s\).
- Select the unfinalized vertex \(u\) with smallest tentative distance.
- Finalize \(u\).
- For each appropriate neighbor \(v\), test whether \(d(u)+w(u,v)
- If so, update \(d(v)\) and record \(u\) as predecessor of \(v\).
- Repeat until the desired vertices are finalized.
Example: Full Shortest-Path Workflow
Suppose a graph has weighted edges
\[ w(S,A)=2,\qquad w(S,B)=5,\qquad w(A,B)=1,\qquad w(A,C)=4,\qquad w(B,C)=2,\qquad w(C,T)=3. \]Starting from \(S\),
\[ d(A)=2,\qquad d(B)=5. \]Through \(A\),
\[ d(B)=2+1=3 \]and
\[ d(C)=2+4=6. \]Through \(B\),
\[ d(C)=3+2=5. \]Finally,
\[ d(T)=5+3=8. \]The shortest route is
\[ \boxed{S,A,B,C,T} \]with total weight
\[ \boxed{8}. \]Practice 1: Path Weight
A path uses edges with weights
\[ 3,\qquad4,\qquad6. \]Find its total weight.
Practice 2: Shortest versus Fewest Edges
Route \(P_1\) uses two edges of weights \(8\) and \(7\).
Route \(P_2\) uses three edges of weights \(3\), \(4\), and \(2\).
Which route is shorter by total weight?
Practice 3: Unweighted Distance
In an unweighted graph, the shortest path from \(u\) to \(v\) uses four edges.
What is the graph distance \(d(u,v)\)?
Practice 4: Dijkstra Initialization
In Dijkstra's algorithm with source \(s\), what tentative distance is assigned initially to \(s\)? What is assigned to every other vertex?
Practice 5: Relaxation
Suppose
\[ d(u)=7,\qquad w(u,v)=3,\qquad d(v)=12. \]What should the new value of \(d(v)\) be after relaxation through \(u\)?
Practice 6: No Improvement
Suppose
\[ d(u)=6,\qquad w(u,v)=5,\qquad d(v)=9. \]Should \(d(v)\) change?
Practice 7: Directed Distance
In a directed graph, must
\[ d(u,v)=d(v,u) \]always hold?
Practice 8: Multiple Shortest Paths
Two different \(a\)-\(b\) paths both have total weight \(11\), and no \(a\)-\(b\) path has smaller weight.
What is \(d(a,b)\)?
Practice 9: Negative Weight
A graph contains a negative-weight edge.
Should ordinary Dijkstra's algorithm be used?
Practice 10: Identify the Error
A student says, “The direct edge from \(A\) to \(D\) has weight \(9\), so it must be the shortest route because it uses only one edge.”
Explain the error.
Practice Answers
Practice 1
Add the weights:
\[ 3+4+6=13. \] \[ \boxed{13}. \]Practice 2
For \(P_1\),
\[ 8+7=15. \]For \(P_2\),
\[ 3+4+2=9. \]Therefore,
\[ \boxed{P_2\text{ has the smaller total weight}}. \]Practice 3
In an unweighted graph, distance is the minimum number of edges:
\[ \boxed{d(u,v)=4}. \]Practice 4
Initialize
\[ \boxed{d(s)=0} \]and
\[ \boxed{d(v)=\infty\text{ for every }v\ne s}. \]Practice 5
The route through \(u\) gives
\[ 7+3=10. \]Since \(10<12\),
\[ \boxed{d(v)=10}. \]Practice 6
The route through \(u\) would cost
\[ 6+5=11. \]Since the current value \(9\) is smaller,
\[ \boxed{d(v)\text{ remains }9}. \]Practice 7
No. Direction may make the two route sets different.
\[ \boxed{d(u,v)\text{ need not equal }d(v,u)}. \]Practice 8
The minimum path weight is \(11\), even though more than one path attains it.
\[ \boxed{d(a,b)=11}. \]Practice 9
No. Ordinary Dijkstra's algorithm assumes nonnegative edge weights.
\[ \boxed{\text{Use a method designed for negative weights instead.}} \]Practice 10
A route with more edges may have a smaller total weight.
The student must compare the cumulative weights of all candidate routes, not merely the number of edges.
What to Remember
- A shortest path minimizes total path weight.
- Shortest does not necessarily mean fewest edges.
- In an unweighted graph, shortest-path distance counts edges.
- In directed graphs, distance may be asymmetric.
- Dijkstra's algorithm solves single-source shortest paths with nonnegative edge weights.
- Relaxation updates a tentative distance when a cheaper route is found.
- Predecessors allow the actual shortest path to be reconstructed.
- Several different shortest paths may have the same minimum weight.
- Dijkstra's algorithm should not be used with negative edge weights.
- A shortest-path tree is different from a minimum spanning tree.
Where We Go Next
Shortest-path methods optimize routes through a weighted graph. Another major network problem asks how much material, traffic, information, or other quantity can move through a directed network subject to capacity limits.
The next lesson, Network Flows, introduces capacities, flow conservation, source and sink vertices, and maximum-flow reasoning.