Shortest path problem Study Guide

📖 Core Concepts Shortest Path – a path between two vertices whose total edge weight ( \(\displaystyle \sum{e\in\text{path}} w(e)\) ) is minimal. Graph types – undirected (edges usable both ways) vs. directed (must follow arc direction). Path length \(k\) – number of consecutive edges in the sequence. Unit‑weight case – when every edge weight = 1, the shortest path = the path with the fewest edges. Problem variants Single‑source: shortest paths from one source to all vertices. Single‑pair: shortest path between a given source‑target pair. All‑pairs: shortest paths for every unordered vertex pair. Negative‑weight handling – only Bellman‑Ford can tolerate negative edges and detect negative cycles. --- 📌 Must Remember Dijkstra → works only with non‑negative weights. Bellman‑Ford → handles negative weights; also tells you if a negative cycle exists. A\ → single‑pair search that needs an admissible heuristic (never overestimates true cost). Floyd‑Warshall → all‑pairs, dense graphs, \(O(V^{3})\) time. Johnson → all‑pairs on sparse graphs; re‑weights edges to be non‑negative, then runs Dijkstra from each vertex. BFS → shortest paths in unweighted (unit‑weight) undirected graphs, \(O(V+E)\). Topological‑order algorithm → single‑source on directed acyclic graphs (DAGs), \(Θ(V+E)\). Constrained shortest‑path (budget, mandatory vertices) → NP‑complete. --- 🔄 Key Processes Dijkstra (priority‑queue version) Initialise distance to source = 0, others = ∞. Insert source into min‑heap. Repeatedly extract vertex \(u\) with smallest distance. For each neighbor \(v\), relax: if \(d(u)+w(u,v) < d(v)\) update \(d(v)\) and decrease‑key in heap. Stop when heap empty (all shortest distances found). Bellman‑Ford Set source distance = 0, others = ∞. Relax all edges \(V-1\) times. Perform one more pass: any further relaxation ⇒ negative cycle reachable. A\ Search Open set ← source with priority \(f = g + h\) ( \(g\)=cost so far, \(h\)=heuristic). Pop node with smallest \(f\). For each neighbor, compute tentative \(g\); if smaller, update and push with new \(f\). Stop when target is popped – path is optimal if \(h\) is admissible. Floyd‑Warshall Initialise matrix \(D{ij}\) = weight of edge \((i,j)\) or ∞ if none (0 on diagonal). For each intermediate vertex \(k\): \[ D{ij} = \min\bigl(D{ij},\; D{ik} + D{kj}\bigr) \] After three nested loops, \(D\) holds all‑pairs shortest distances. Johnson (sparse) Add a new vertex \(s\) connected to every vertex with zero‑weight edges. Run Bellman‑Ford from \(s\) to get potential \(h(v)\). Re‑weight each edge: \(w'(u,v)=w(u,v)+h(u)-h(v)\) (guaranteed non‑negative). Run Dijkstra from each vertex using \(w'\); recover original distances by subtracting potentials. --- 🔍 Key Comparisons Dijkstra vs. Bellman‑Ford Weight signs: Dijkstra → non‑negative only; Bellman‑Ford → any (detects negatives). Complexity: Dijkstra (with binary heap) \(O((V+E)\log V)\); Bellman‑Ford \(O(VE)\). BFS vs. Dijkstra Edge weights: BFS → all = 1; Dijkstra → arbitrary non‑negative. Runtime: BFS \(O(V+E)\); Dijkstra \(O((V+E)\log V)\). Floyd‑Warshall vs. Johnson Graph density: Floyd‑Warshall best for dense graphs; Johnson best for sparse graphs. Complexity: Floyd‑Warshall \(O(V^{3})\); Johnson \(O(VE + V^{2}\log V)\). Topological‑order algorithm vs. General Dijkstra Graph type: DAG only vs. any non‑negative‑weight graph. Speed: \(Θ(V+E)\) (linear) vs. \(O((V+E)\log V)\). --- ⚠️ Common Misunderstandings “Dijkstra works with negative edges” – false; a single negative edge can produce an incorrect distance. “A\ always faster than Dijkstra” – only if you have a good admissible heuristic; a poor heuristic may degrade to Dijkstra. “Floyd‑Warshall gives a path, not just distance” – you must also maintain a predecessor matrix to reconstruct paths. “Johnson eliminates the need for Bellman‑Ford” – Johnson starts with Bellman‑Ford to compute potentials; it cannot bypass it. “Unit‑weight graphs need Dijkstra” – BFS is optimal and simpler for unit weights. --- 🧠 Mental Models / Intuition “Relaxation = tightening a rope” – each edge relaxation can only pull the distance estimate down, never up. “Potential re‑weighting (Johnson) is like raising the floor – you add a constant to each vertex so that every edge becomes non‑negative, but the relative differences (shortest paths) stay unchanged. “A\ heuristic is a compass – as long as it never points past the destination (admissible), it guides you straight without detours. “Negative‑cycle detection = walking around a loop and ending up cheaper each time” – Bellman‑Ford’s extra pass catches this endless “discount”. --- 🚩 Exceptions & Edge Cases Zero‑weight cycles – Dijkstra still works (no negative weights), but care needed to avoid infinite loops in implementations that don’t mark visited edges. Multiple edges between same vertices – treat each as a separate edge; Dijkstra will pick the lighter one during relaxation. Disconnected graph – unreachable vertices retain distance = ∞; algorithms should handle this gracefully. Sparse graph with large integer weights – using a Fibonacci heap can improve Dijkstra’s runtime to \(O(E + V\log V)\). --- 📍 When to Use Which Non‑negative weights, single source → Dijkstra (binary heap) or Fibonacci heap for very large sparse graphs. Negative weights present → Bellman‑Ford (detect cycles) or Johnson (if all‑pairs needed). Single pair, good heuristic available → A\ (especially in grids or road maps). Unit weights, any graph → BFS (fastest linear time). DAG, single source → Topological‑order algorithm (linear). Dense graph, all‑pairs → Floyd‑Warshall. Sparse graph, all‑pairs → Johnson (re‑weight + Dijkstra). Network flow augmentation → use shortest‑augmenting‑path (e.g., Bellman‑Ford or Dijkstra on residual graph). --- 👀 Patterns to Recognize “All edge weights = 1” → immediately think BFS. “Graph is a DAG” → look for topological order solution. “Negative edge but no negative cycle” → Bellman‑Ford is the safe choice. “Problem asks for many source‑destination pairs” → consider all‑pairs algorithms (Floyd‑Warshall or Johnson). “Heuristic given (e.g., Euclidean distance) for grid navigation” → A\ is likely intended. “Sparse graph + need all‑pairs” → Johnson beats cubic Floyd‑Warshall. --- 🗂️ Exam Traps Choosing Dijkstra with a negative edge – the answer will be wrong; the test may include a single negative weight to catch this. Confusing BFS and Dijkstra – if the graph is unweighted, picking Dijkstra is unnecessary but still correct; however, they may ask for linear‑time solution, so BFS is the expected answer. Assuming Floyd‑Warshall works on huge graphs – time limit may make it infeasible; the correct choice is Johnson for sparse graphs. Neglecting to rebuild original distances after Johnson’s re‑weighting – answer choices that omit the subtraction of potentials are incorrect. Mistaking “shortest augmenting path” for “maximum flow” – the augmenting‑path step is part of the Edmonds‑Karp (BFS) or successive shortest path algorithms, not a direct flow formula. Mixing up “single‑source” vs. “single‑pair” – a question may phrase “find the shortest path from A to B” (single‑pair) – A\ or Dijkstra (with heuristic) is expected, not an all‑pairs method. ---