Shortest Paths

Table of contents

1. Weighted shortest paths
2. Dijkstra’s algorithm
3. Dijkstra’s demo
4. Why Dijkstra’s works
5. Dijkstra’s order
6. Negative edge weights
7. Real-world routing

Weighted shortest paths

Dijkstra’s algorithm

Dijkstra’s demo

Why Dijkstra’s works

Dijkstra’s order

Consider the following weighted directed acyclic graph. We want to find the shortest paths tree starting from A.

Question 1

During the execution of Dijkstra’s algorithm on a non-negative edge-weighted graph, when do we know that we’ve found the shortest path to a node?

• When we first relax an edge adjacent to the node.
• When the distTo entry for the node is not infinity.
• When the edgeTo entry for the node is not null.
• When the known entry for the node is checked.

Question 2

What is the distance value for the shortest path from A to G, i.e. distTo[G]?

Question 3

Give the order in which Dijkstra’s algorithm marks each node as known, i.e. determines the shortest path to that node.

Negative edge weights

Consider the following weighted directed acyclic graph. We want to find the shortest paths tree starting from A.

Question 1

Explain in plain English why Dijkstra’s algorithm isn’t guaranteed to work if there are negative edge weights in the graph.

Question 2

Which edge, if replaced with the weight -100, would cause Dijkstra’s algorithm to compute an incorrect shortest paths tree starting from A?

• A–B
• A–D
• B–C
• B–H
• C–F
• C–G
• D–E
• E–H
• F–G
• H–G

Question 3

Consider the edge from the previous question. Instead of -100, what is the least-negative (most-positive) integer edge weight that would still cause Dijkstra’s algorithm to compute an incorrect shortest paths tree starting from A?

Real-world routing

Suppose we have a weighted undirected graph that represents all of the footpaths in the Seattle region, where each node represents an intersection and each edge represents the distance between intersections. Assume there are no speed limits on footpaths—this assumption avoids the concern in road networks about physical distance vs. actual travel time.

In the real world, however, the best path from A to B might not be the absolute shortest path.

Question 1

Give an affordance analysis of weighted shortest paths in the context of real-world footpath routing. How do the affordances of the returned solution confer benefits and harms to different people who want to find their best path? Consider especially how minoritized groups may be affected.

Question 2

Consider the weighted k-shortest paths problem, which finds not only the absolute shortest path in a weighted graph, but also the next k − 1 shortest paths. Give an affordance analysis of weighted k-shortest paths in the context of real-world footpath routing.