# Shortest Paths

## Table of contents

- Weighted shortest paths
- Dijkstra’s algorithm
- Dijkstra’s demo
- Why Dijkstra’s works
- Dijkstra’s order
- Negative edge weights
- 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]`

?

## Explanation

**A–B–C–F–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.

## Explanation

Dijkstra’s algorithm determines which node to visit next based on its distance from the start 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.