Shortest-Path Algorithms for a City Road Network

A city road network can be modeled as a graph where vertices denote locations and edges denote roads. The design question is: given a source location, which algorithm should compute the shortest path under different road-length assumptions? The correct choice depends entirely on the edge-weight model.2

For the three cases in the prompt, the standard choices are:

This is fundamentally a single-source shortest path decision problem. If one source location is fixed and we want distances to many other locations, these three algorithms form the canonical toolkit.2

A useful conceptual map is:

Footnotes

1. Shortest Path Algorithm Comparison: Two Questions Decide - Concise comparison of BFS, Dijkstra, and Bellman-Ford by graph weight conditions and complexity. ↩ ↩²

2. Bellman-Ford - finding shortest paths with negative weights - Detailed explanation of Bellman-Ford, repeated relaxation, and negative-cycle detection. ↩ ↩²

3. Understanding connection between minimum spanning tree, shortest path, breadth first and depth first traversal - Summarizes the CLRS statement that BFS gives shortest-path distances in unweighted graphs. ↩

4. Dijkstra's algorithm - Wikipedia - Notes that BFS is a special case of Dijkstra on unweighted graphs. ↩

5. Dijkstra's algorithm - Wikipedia - Describes Dijkstra’s purpose, nonnegative-weight requirement, and standard complexity. ↩ ↩²

6. Chapter 12 Shortest Paths (CMU lecture notes) - Explains why Dijkstra works for nonnegative edges and fails with negative ones. ↩

7. Bellman–Ford algorithm - Wikipedia - Describes Bellman-Ford’s $O(|V||E|)$ runtime, handling of negative weights, and negative-cycle detection. ↩

Case (i): All Roads Have Equal Length $\rightarrow$ BFS

If every road has identical length, then the total path cost is proportional to the number of roads used. In that setting, minimizing distance is the same as minimizing the number of edges on the path. Breadth-First Search explores the graph level by level, so it discovers every vertex first through a path with the minimum number of edges.2

Why this works:

• BFS visits all vertices at distance $1$ edge from the source before any at distance $2$.
• Then it visits all vertices at distance $2$ before any at distance $3$.
• Therefore, the first time a vertex is reached, BFS has found a shortest path in terms of edge count.

If every road length is exactly $L$, then a path with $k$ edges has total length $kL$. Since $L$ is constant, minimizing $kL$ is equivalent to minimizing $k$:

$$\operatorname{cost}(P)=kL$$

So:

$$\arg\min_P \operatorname{cost}(P)=\arg\min_P k$$

That is exactly what BFS optimizes.2

In practical city terms, if each road segment is treated as equally costly—perhaps in a coarse routing model where every block is approximated as one unit—BFS is both correct and efficient. Its time complexity is:

$$O(|V|+|E|)$$

where $|V|$ is the number of locations and $|E|$ is the number of roads.2

Footnotes

1. Understanding connection between minimum spanning tree, shortest path, breadth first and depth first traversal - Summarizes the CLRS statement that BFS gives shortest-path distances in unweighted graphs. ↩ ↩² ↩³ ↩⁴ ↩⁵

2. Dijkstra's algorithm - Wikipedia - Notes that BFS is a special case of Dijkstra on unweighted graphs. ↩ ↩²

3. Shortest Path Algorithm Comparison: Two Questions Decide - Concise comparison of BFS, Dijkstra, and Bellman-Ford by graph weight conditions and complexity. ↩

Case (ii): Roads Have Varying Lengths but No Negative Lengths $\rightarrow$ Dijkstra’s Algorithm

When road lengths vary, minimizing the number of roads is no longer enough. A route with fewer roads may still be longer in total distance than a route with more roads. We therefore need an algorithm that minimizes the sum of edge weights.

Dijkstra’s algorithm is the standard choice when all road lengths are nonnegative. It maintains a priority queue of tentative distances and repeatedly finalizes the not-yet-processed location with smallest known distance.2

The key correctness condition is nonnegativity. Suppose the algorithm extracts a location $u$ with smallest tentative distance. If every edge weight is at least $0$, then any alternative path reaching $u$ later through unexplored vertices cannot be shorter, because extending a path cannot reduce its total cost.2 This greedy argument fails if negative edges exist.

Formally, if path cost is the sum of edge lengths,

$$\operatorname{dist}(v)=\min_{P:s\leadsto v}\sum_{e\in P} w(e)$$

then Dijkstra computes these values correctly when

$$w(e)\ge 0 \quad \text{for all edges } e$$

Its runtime depends on implementation. With a binary heap priority queue, the standard complexity is approximately

$$O((|V|+|E|)\log |V|)$$

or equivalently $O(|E|\log |V|)$ on sparse graphs.3

This makes Dijkstra highly suitable for realistic road networks, since actual road distances and travel times are usually nonnegative.

Footnotes

1. Dijkstra's algorithm - Wikipedia - Describes Dijkstra’s purpose, nonnegative-weight requirement, and standard complexity. ↩ ↩² ↩³ ↩⁴ ↩⁵

2. Chapter 12 Shortest Paths (CMU lecture notes) - Explains why Dijkstra works for nonnegative edges and fails with negative ones. ↩ ↩² ↩³

3. Shortest Path Algorithm Comparison: Two Questions Decide - Concise comparison of BFS, Dijkstra, and Bellman-Ford by graph weight conditions and complexity. ↩

Why Dijkstra Is Not Appropriate for Negative Roads

If a negative road exists, a path that looks longer initially may later become shorter after taking that negative edge. This breaks the greedy invariant used by Dijkstra.2

Example idea:

• Suppose the current best path to $b$ is $2$.
• Another node $a$ has current distance $3$.
• There is an edge from $a$ to $b$ with weight $-2$.
• Then going through $a$ yields total cost $1$, better than $2$.

A greedy algorithm that finalized $b$ too early would be wrong. Therefore, Dijkstra should not be used when negative edges are possible.3

In this graph, the direct tentative route to $B$ has cost $2$, but the path $S \rightarrow A \rightarrow B$ has cost $1$. This is exactly the kind of situation that invalidates Dijkstra’s greedy choice.

Footnotes

1. Bellman-Ford - finding shortest paths with negative weights - Detailed explanation of Bellman-Ford, repeated relaxation, and negative-cycle detection. ↩ ↩²

2. Chapter 12 Shortest Paths (CMU lecture notes) - Explains why Dijkstra works for nonnegative edges and fails with negative ones. ↩ ↩² ↩³ ↩⁴

3. Dijkstra's algorithm - Wikipedia - Describes Dijkstra’s purpose, nonnegative-weight requirement, and standard complexity. ↩

Case (iii): Some Roads Have Negative Lengths $\rightarrow$ Bellman–Ford

If some edges are negative, the appropriate algorithm is Bellman–Ford.2 It does not greedily finalize vertices. Instead, it repeatedly relaxes all edges, gradually propagating improvements through the graph.

Its logic is based on the fact that any shortest simple path contains at most $|V|-1$ edges. Therefore, if there is no negative cycle reachable from the source, repeating edge relaxation $|V|-1$ times is sufficient to compute correct shortest distances.2

The relaxation rule for an edge $(u,v)$ with weight $w(u,v)$ is:

$$\text{if } d[u] + w(u,v) < d[v], \text{ then set } d[v] = d[u] + w(u,v)$$

After $|V|-1$ full passes over all edges, one more pass is used to test for a negative cycle.2 If any distance can still be improved, then a negative cycle is reachable, and no finite shortest path exists for affected vertices because the path cost can be driven downward without bound.2

The time complexity is:

$$O(|V||E|)$$

which is slower than Dijkstra, but it is the correct general-purpose method when negative weights are allowed.3

Footnotes

1. Bellman-Ford - finding shortest paths with negative weights - Detailed explanation of Bellman-Ford, repeated relaxation, and negative-cycle detection. ↩ ↩² ↩³ ↩⁴ ↩⁵

2. Bellman–Ford algorithm - Wikipedia - Describes Bellman-Ford’s $O(|V||E|)$ runtime, handling of negative weights, and negative-cycle detection. ↩ ↩² ↩³ ↩⁴ ↩⁵

3. Shortest Path Algorithm Comparison: Two Questions Decide - Concise comparison of BFS, Dijkstra, and Bellman-Ford by graph weight conditions and complexity. ↩

Comparative Justification

The three algorithm choices are justified by the mathematical structure of the graph weights, not by superficial implementation preference.

1. Equal weights $\rightarrow$ BFS

When all roads have the same cost, total path length is proportional to edge count. BFS explores in increasing number of edges from the source, so it is optimal and asymptotically cheaper than weighted algorithms.3

2. Nonnegative varying weights $\rightarrow$ Dijkstra

When weights differ but remain nonnegative, a greedy frontier-expansion strategy is sound. The first time the minimum tentative vertex is extracted, its shortest distance is final.2 This makes Dijkstra both correct and efficient for realistic road lengths and travel times.

3. Negative weights $\rightarrow$ Bellman–Ford

Negative edges invalidate Dijkstra’s greedy assumption. Bellman–Ford remains correct because it does not finalize nodes prematurely; instead, it allows improvements to propagate across the graph through repeated relaxation.3 It also adds the crucial ability to detect negative cycles.

A compact decision rule is:

$$\text{Algorithm}= \begin{cases} \text{BFS}, & \text{if all weights are equal} \\ \text{Dijkstra}, & \text{if } w(e)\ge 0 \text{ for all } e \\ \text{Bellman-Ford}, & \text{if some } w(e)<0 \end{cases}$$

Footnotes

1. Shortest Path Algorithm Comparison: Two Questions Decide - Concise comparison of BFS, Dijkstra, and Bellman-Ford by graph weight conditions and complexity. ↩

2. Understanding connection between minimum spanning tree, shortest path, breadth first and depth first traversal - Summarizes the CLRS statement that BFS gives shortest-path distances in unweighted graphs. ↩

3. Dijkstra's algorithm - Wikipedia - Notes that BFS is a special case of Dijkstra on unweighted graphs. ↩

4. Dijkstra's algorithm - Wikipedia - Describes Dijkstra’s purpose, nonnegative-weight requirement, and standard complexity. ↩

5. Chapter 12 Shortest Paths (CMU lecture notes) - Explains why Dijkstra works for nonnegative edges and fails with negative ones. ↩ ↩²

6. Bellman-Ford - finding shortest paths with negative weights - Detailed explanation of Bellman-Ford, repeated relaxation, and negative-cycle detection. ↩

7. Bellman–Ford algorithm - Wikipedia - Describes Bellman-Ford’s $O(|V||E|)$ runtime, handling of negative weights, and negative-cycle detection. ↩

Final Answer

For a city graph:

1. If all roads have equal length, use BFS, because shortest distance is equivalent to the fewest number of roads traversed.2
2. If roads have varying lengths but none are negative, use Dijkstra’s algorithm, because its greedy selection is correct under nonnegative weights and it is efficient.2
3. If some roads have negative lengths, use Bellman–Ford, because it correctly handles negative edges and can detect negative cycles where shortest paths are not well-defined.2

Thus, the algorithm choice is determined by the weight properties of the road network graph, and each recommendation follows directly from the correctness conditions of the corresponding shortest-path algorithm.3

Footnotes

1. Understanding connection between minimum spanning tree, shortest path, breadth first and depth first traversal - Summarizes the CLRS statement that BFS gives shortest-path distances in unweighted graphs. ↩

2. Dijkstra's algorithm - Wikipedia - Notes that BFS is a special case of Dijkstra on unweighted graphs. ↩

3. Dijkstra's algorithm - Wikipedia - Describes Dijkstra’s purpose, nonnegative-weight requirement, and standard complexity. ↩ ↩²

4. Chapter 12 Shortest Paths (CMU lecture notes) - Explains why Dijkstra works for nonnegative edges and fails with negative ones. ↩

5. Bellman-Ford - finding shortest paths with negative weights - Detailed explanation of Bellman-Ford, repeated relaxation, and negative-cycle detection. ↩ ↩²

6. Bellman–Ford algorithm - Wikipedia - Describes Bellman-Ford’s $O(|V||E|)$ runtime, handling of negative weights, and negative-cycle detection. ↩

7. Shortest Path Algorithm Comparison: Two Questions Decide - Concise comparison of BFS, Dijkstra, and Bellman-Ford by graph weight conditions and complexity. ↩