Lesson 26.3 · Shortest Paths
Changing What "Cost" Means
Dijkstra works for any path cost that never gets better as the path grows: sums, maximums (bottlenecks), products of probabilities ≤ 1, and extra state such as stops used.
10 min
Think of it like this
Planning a hike by the steepest climb instead of the total distance: you still explore the gentlest options first, but you compare routes by their worst climb.
1.Same loop, different combine
Minimax (bottleneck): cost of a path = its largest edge. Combine with max(d, w) instead of d + w (Path With Minimum Effort, Swim in Rising Water).
Maximum probability: combine with p × w and use a max-heap; probabilities never increase along a path, so the greedy argument still works.
Counting shortest paths: alongside dist, keep ways[]. A strictly shorter route resets ways[v] to ways[u]; an equal one adds ways[u].
State-expanded graphs: if the cost depends on extra information (stops used, keys held, fuel left), make the node a pair (vertex, state).
Remember
- The combine must never improve as the path grows.
- Max-heap for maximisation.
- Add state to nodes when needed.
Common mistakes
- Using Dijkstra for longest paths (adding positive weights makes paths better, which breaks the greedy rule).