Skip to content

Shortest Paths Ladder

This ladder is about learning to choose the shortest-path algorithm from the edge model instead of memorizing Dijkstra as a default hammer.

Current repo shape: the unweighted branch has a cleaner internal anchor than the weighted branch. Treat this lane as topic + template backed, with QOS as the weighted compare point rather than the first weighted warm-up.

Who This Is For

Use this ladder if:

  • weighted vs unweighted modeling still causes hesitation
  • you know Dijkstra, but not when BFS or 0-1 BFS is cleaner
  • path restoration and stale-entry handling still feel fragile

Warm-Up

  • BFS on an unweighted graph
  • shortest path restoration with parents
  • compare BFS against Dijkstra on the same model

Target skill:

  • choose the lightest valid shortest-path method

Core

  • Dijkstra with nonnegative weights
  • reverse shortest paths
  • choose between BFS, 0-1 BFS, and Dijkstra

Target skill:

  • reason from weight model first, implementation second

Stretch

Target skill:

  • use shortest paths as a base layer for richer reconstruction or DP problems

Repo Anchors And Compare Points

Use this ladder in two passes:

  1. learn the family chooser from Shortest Paths, then stabilize the unweighted baseline through Message Route
  2. use QOS as the weighted compare point after the family choice already feels plausible

Retrieval Layer

There is still only one direct weighted repo note in this ladder, so if the family feels thin do not browse randomly. Reopen:

  • Message Route for the unweighted baseline
  • QOS for weighted reconstruction after the topic page has already framed the right algorithm
  • Shortest Paths for the full chooser

Exit Criteria

You are ready to move on when:

  • you never use Dijkstra on negative edges
  • you can explain stale heap entries and skip them confidently
  • you know when reverse-graph shortest paths simplify the problem

External Practice