[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":93,"_73":94,"_35":95},"articles",{"_11":12,"_13":14,"_15":16,"_17":16,"_18":19,"_20":21,"_22":23,"_24":23,"_25":16,"_26":27},"content",[30],"pageable",{"_28":21,"_29":19},"totalElements",1,"totalPages","size",10,"number",0,"first",true,"last","numberOfElements","empty",false,"page_number","page_size",{"_31":32,"_33":34,"_35":36,"_37":38,"_11":39,"_40":-5,"_41":23,"_42":27,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":52,"_54":55,"_56":57,"_58":59,"_60":52,"_61":62,"_63":64,"_65":66,"_67":68,"_69":70,"_71":72},"id",39,"title","Shortest Path Algorithms","slug","algorithms-part-12-shortest-path","excerpt","Implement Dijkstra's, Bellman-Ford for negative weights, Floyd-Warshall for all pairs, and A* with heuristics. Detect negative cycles.","# Algorithms Compendium Part 12: Shortest Path Algorithms\n\nFinding the shortest path between two points is one of computing's most practical problems. GPS navigation, network routing, game AI pathfinding, and social network analysis all rely on shortest path algorithms. This article covers the four essential algorithms: Dijkstra's for non-negative weights, Bellman-Ford for negative weights, Floyd-Warshall for all pairs, and A* for heuristic-guided search.\n\n## 📋 At a Glance\n\n| Algorithm | Time | Space | Handles Negative | Best For |\n|-----------|------|-------|------------------|----------|\n| Dijkstra (binary heap) | O((V+E) log V) | O(V) | No | Single source, non-negative |\n| Bellman-Ford | O(VE) | O(V) | Yes (detects cycles) | Negative weights |\n| Floyd-Warshall | O(V³) | O(V²) | Yes (detects cycles) | All pairs, dense graphs |\n| A* | O(E) best, O(V²) worst | O(V) | No | Single pair with heuristic |\n\n---\n\n## 🎯 What You'll Learn\n\nAfter reading this article, you will be able to:\n\n- **Implement Dijkstra's algorithm** with proper priority queue usage\n- **Handle negative weights** using Bellman-Ford\n- **Compute all-pairs shortest paths** with Floyd-Warshall\n- **Apply A* search** with admissible heuristics\n- **Detect negative cycles** that make shortest path undefined\n- **Choose the right algorithm** based on graph characteristics\n\n---\n\n## 🔥 Production Story: The Logistics Routing Disaster\n\nA delivery company's routing system calculated optimal routes for 500 daily deliveries. After adding \"discount roads\" with negative costs (toll rebates), the system started producing impossible routes.\n\n```java\n// ❌ Initial approach: Dijkstra for all routes\npublic class RoutingService {\n public Route findBestRoute(Graph roadNetwork, int origin, int destination) {\n return dijkstra(roadNetwork, origin, destination);\n }\n\n private Route dijkstra(Graph g, int src, int dst) {\n int[] dist = new int[g.getVertices()];\n Arrays.fill(dist, Integer.MAX_VALUE);\n dist[src] = 0;\n\n PriorityQueue pq = new PriorityQueue<>(\n Comparator.comparingInt(a -> a[1])\n );\n pq.offer(new int[]{src, 0});\n\n while (!pq.isEmpty()) {\n int[] curr = pq.poll();\n int u = curr[0], d = curr[1];\n\n if (d > dist[u]) continue;\n\n for (Edge e : g.neighbors(u)) {\n int newDist = dist[u] + e.weight(); // Bug with negative weights!\n if (newDist < dist[e.to()]) {\n dist[e.to()] = newDist;\n pq.offer(new int[]{e.to(), newDist});\n }\n }\n }\n return buildRoute(dist, dst);\n }\n}\n```\n\n**The problem:** Dijkstra assumes once a vertex is processed, its distance is final. Negative edges violate this assumption - a \"longer\" path through negative edges might be shorter!\n\n```text\nExample failure:\n A ──(5)──→ B ──(2)──→ D\n │ ↑\n └──(1)──→ C ──(-4)───┘\n\nDijkstra from A:\n1. Process A: dist[B]=5, dist[C]=1\n2. Process C (smallest): dist[C]=1 is final ✗\n3. Process B: dist[D]=7\n4. Process D: dist[D]=7 is final ✗\n\nBut actual shortest: A→C→D = 1+(-4) = -3, not 7!\n```\n\n**The fix:**\n\n```java\n// ✅ Use Bellman-Ford for graphs with negative weights\npublic class SafeRoutingService {\n public Route findBestRoute(Graph roadNetwork, int origin, int destination) {\n // Check for negative edges\n boolean hasNegative = hasNegativeEdges(roadNetwork);\n\n if (hasNegative) {\n BellmanFordResult result = bellmanFord(roadNetwork, origin);\n if (result.hasNegativeCycle()) {\n throw new InvalidRouteException(\"Negative cycle detected - no valid route\");\n }\n return buildRoute(result.distances(), result.predecessors(), destination);\n } else {\n return dijkstra(roadNetwork, origin, destination);\n }\n }\n\n private BellmanFordResult bellmanFord(Graph g, int src) {\n int n = g.getVertices();\n int[] dist = new int[n];\n int[] pred = new int[n];\n Arrays.fill(dist, Integer.MAX_VALUE);\n Arrays.fill(pred, -1);\n dist[src] = 0;\n\n // Relax all edges V-1 times\n for (int i = 0; i < n - 1; i++) {\n for (int u = 0; u < n; u++) {\n if (dist[u] == Integer.MAX_VALUE) continue;\n for (Edge e : g.neighbors(u)) {\n if (dist[u] + e.weight() < dist[e.to()]) {\n dist[e.to()] = dist[u] + e.weight();\n pred[e.to()] = u;\n }\n }\n }\n }\n\n // Check for negative cycle\n boolean hasNegativeCycle = false;\n for (int u = 0; u < n; u++) {\n if (dist[u] == Integer.MAX_VALUE) continue;\n for (Edge e : g.neighbors(u)) {\n if (dist[u] + e.weight() < dist[e.to()]) {\n hasNegativeCycle = true;\n break;\n }\n }\n }\n\n return new BellmanFordResult(dist, pred, hasNegativeCycle);\n }\n}\n```\n\n**The lesson:** Algorithm selection isn't just about performance - it's about correctness. Using Dijkstra on negative-weight graphs gives wrong answers silently.\n\n---\n\n## 🧠 Mental Model: Shortest Path Algorithm Selection\n\n```text\nSHORTEST PATH DECISION TREE\n━━━━━━━━━━━━━━━━━━━━━━━━━━━\n\nWhat do you need?\n│\n├── Single source to single destination?\n│ │\n│ ├── No negative weights?\n│ │ ├── Have good heuristic? ──→ A*\n│ │ └── No heuristic? ──→ Dijkstra\n│ │\n│ └── Has negative weights?\n│ └── Bellman-Ford (or check for cycle first)\n│\n├── Single source to ALL destinations?\n│ │\n│ ├── No negative weights? ──→ Dijkstra\n│ └── Has negative weights? ──→ Bellman-Ford\n│\n└── ALL pairs shortest paths?\n │\n ├── Dense graph (E ≈ V²)? ──→ Floyd-Warshall\n └── Sparse graph? ──→ Run Dijkstra/BF from each vertex\n```\n\n---\n\n## 🔬 Deep Dive: Dijkstra's Algorithm\n\n### 🎮 Try It Yourself\n\nWatch Dijkstra's algorithm find shortest paths step by step. Observe how the algorithm greedily selects the minimum distance vertex and relaxes edges:\n\n```visualizer-dijkstra\n```\n\n### The Greedy Insight\n\nDijkstra works by greedily selecting the unvisited vertex with minimum distance. With non-negative weights, this greedy choice is always correct.\n\n```text\nDIJKSTRA'S INVARIANT\n━━━━━━━━━━━━━━━━━━━━\n\nAt each step:\n- Vertices in \"processed\" set have final shortest distances\n- PQ contains vertices with tentative distances\n- Greedy choice: process vertex with smallest tentative distance\n\nWhy it works (non-negative weights):\n- If we pick vertex u with distance d[u]\n- Any other path to u must go through another unprocessed vertex v\n- But d[v] ≥ d[u] (we picked u because it's smallest)\n- And edge from v to u adds ≥ 0\n- So other path ≥ d[u], meaning d[u] is optimal\n```\n\n### Implementation with Priority Queue\n\n```java\npublic class Dijkstra {\n /**\n * Dijkstra's shortest path algorithm.\n *\n * Time: O((V + E) log V) with binary heap\n * Space: O(V)\n *\n * @return distances from source to all vertices\n */\n public static int[] shortestPaths(WeightedGraph graph, int source) {\n int n = graph.getVertices();\n int[] dist = new int[n];\n Arrays.fill(dist, Integer.MAX_VALUE);\n dist[source] = 0;\n\n // PQ contains [vertex, distance]\n PriorityQueue pq = new PriorityQueue<>(\n Comparator.comparingInt(a -> a[1])\n );\n pq.offer(new int[]{source, 0});\n\n while (!pq.isEmpty()) {\n int[] curr = pq.poll();\n int u = curr[0];\n int d = curr[1];\n\n // Skip if we've already found a better path\n if (d > dist[u]) continue;\n\n for (WeightedGraph.Edge e : graph.neighbors(u)) {\n int v = e.to();\n int newDist = dist[u] + e.weight();\n\n if (newDist < dist[v]) {\n dist[v] = newDist;\n pq.offer(new int[]{v, newDist});\n }\n }\n }\n\n return dist;\n }\n\n /**\n * Find shortest path and return the actual path.\n */\n public static List shortestPath(WeightedGraph graph,\n int source, int target) {\n int n = graph.getVertices();\n int[] dist = new int[n];\n int[] pred = new int[n];\n Arrays.fill(dist, Integer.MAX_VALUE);\n Arrays.fill(pred, -1);\n dist[source] = 0;\n\n PriorityQueue pq = new PriorityQueue<>(\n Comparator.comparingInt(a -> a[1])\n );\n pq.offer(new int[]{source, 0});\n\n while (!pq.isEmpty()) {\n int[] curr = pq.poll();\n int u = curr[0];\n int d = curr[1];\n\n if (u == target) break; // Early termination\n if (d > dist[u]) continue;\n\n for (WeightedGraph.Edge e : graph.neighbors(u)) {\n int v = e.to();\n int newDist = dist[u] + e.weight();\n\n if (newDist < dist[v]) {\n dist[v] = newDist;\n pred[v] = u;\n pq.offer(new int[]{v, newDist});\n }\n }\n }\n\n return reconstructPath(pred, source, target);\n }\n\n private static List reconstructPath(int[] pred, int source, int target) {\n if (pred[target] == -1 && target != source) {\n return Collections.emptyList(); // No path\n }\n\n List path = new ArrayList<>();\n int curr = target;\n while (curr != -1) {\n path.add(curr);\n curr = pred[curr];\n }\n Collections.reverse(path);\n return path;\n }\n}\n```\n\n### Dijkstra with Indexed Priority Queue (Optimized)\n\n```java\npublic class DijkstraOptimized {\n /**\n * Dijkstra with indexed priority queue for O(log V) decrease-key.\n * Better constant factors for dense graphs.\n */\n public static int[] shortestPaths(WeightedGraph graph, int source) {\n int n = graph.getVertices();\n int[] dist = new int[n];\n Arrays.fill(dist, Integer.MAX_VALUE);\n dist[source] = 0;\n\n // IndexedPQ allows updating priorities\n IndexedMinPQ pq = new IndexedMinPQ<>(n);\n pq.insert(source, 0);\n\n while (!pq.isEmpty()) {\n int u = pq.delMin();\n\n for (WeightedGraph.Edge e : graph.neighbors(u)) {\n int v = e.to();\n int newDist = dist[u] + e.weight();\n\n if (newDist < dist[v]) {\n dist[v] = newDist;\n if (pq.contains(v)) {\n pq.decreaseKey(v, newDist);\n } else {\n pq.insert(v, newDist);\n }\n }\n }\n }\n\n return dist;\n }\n\n // Simplified IndexedMinPQ implementation\n static class IndexedMinPQ> {\n private final int[] pq; // Binary heap\n private final int[] qp; // Inverse: qp[pq[i]] = i\n private final T[] keys;\n private int size;\n\n @SuppressWarnings(\"unchecked\")\n IndexedMinPQ(int capacity) {\n pq = new int[capacity + 1];\n qp = new int[capacity];\n keys = (T[]) new Comparable[capacity];\n Arrays.fill(qp, -1);\n }\n\n void insert(int i, T key) {\n size++;\n qp[i] = size;\n pq[size] = i;\n keys[i] = key;\n swim(size);\n }\n\n int delMin() {\n int min = pq[1];\n swap(1, size--);\n sink(1);\n qp[min] = -1;\n keys[min] = null;\n return min;\n }\n\n void decreaseKey(int i, T key) {\n keys[i] = key;\n swim(qp[i]);\n }\n\n boolean contains(int i) { return qp[i] != -1; }\n boolean isEmpty() { return size == 0; }\n\n private void swim(int k) {\n while (k > 1 && greater(k / 2, k)) {\n swap(k, k / 2);\n k = k / 2;\n }\n }\n\n private void sink(int k) {\n while (2 * k <= size) {\n int j = 2 * k;\n if (j < size && greater(j, j + 1)) j++;\n if (!greater(k, j)) break;\n swap(k, j);\n k = j;\n }\n }\n\n private boolean greater(int i, int j) {\n return keys[pq[i]].compareTo(keys[pq[j]]) > 0;\n }\n\n private void swap(int i, int j) {\n int tmp = pq[i];\n pq[i] = pq[j];\n pq[j] = tmp;\n qp[pq[i]] = i;\n qp[pq[j]] = j;\n }\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Bellman-Ford Algorithm\n\n### Handling Negative Weights\n\n```java\npublic class BellmanFord {\n /**\n * Bellman-Ford shortest paths with negative weight handling.\n *\n * Time: O(VE)\n * Space: O(V)\n *\n * @throws NegativeCycleException if negative cycle exists\n */\n public static int[] shortestPaths(WeightedGraph graph, int source)\n throws NegativeCycleException {\n int n = graph.getVertices();\n int[] dist = new int[n];\n Arrays.fill(dist, Integer.MAX_VALUE);\n dist[source] = 0;\n\n // Relax all edges V-1 times\n for (int i = 0; i < n - 1; i++) {\n boolean changed = false;\n\n for (int u = 0; u < n; u++) {\n if (dist[u] == Integer.MAX_VALUE) continue;\n\n for (WeightedGraph.Edge e : graph.neighbors(u)) {\n int v = e.to();\n long newDist = (long) dist[u] + e.weight();\n\n if (newDist < dist[v]) {\n dist[v] = (int) newDist;\n changed = true;\n }\n }\n }\n\n // Early termination if no changes\n if (!changed) break;\n }\n\n // Check for negative cycle (V-th iteration)\n for (int u = 0; u < n; u++) {\n if (dist[u] == Integer.MAX_VALUE) continue;\n\n for (WeightedGraph.Edge e : graph.neighbors(u)) {\n if (dist[u] + e.weight() < dist[e.to()]) {\n throw new NegativeCycleException(\n \"Graph contains negative-weight cycle\");\n }\n }\n }\n\n return dist;\n }\n\n /**\n * Find the actual negative cycle if one exists.\n */\n public static List findNegativeCycle(WeightedGraph graph, int source) {\n int n = graph.getVertices();\n int[] dist = new int[n];\n int[] pred = new int[n];\n Arrays.fill(dist, Integer.MAX_VALUE);\n Arrays.fill(pred, -1);\n dist[source] = 0;\n\n int cycleVertex = -1;\n\n // V iterations (one extra to detect cycle)\n for (int i = 0; i < n; i++) {\n cycleVertex = -1;\n\n for (int u = 0; u < n; u++) {\n if (dist[u] == Integer.MAX_VALUE) continue;\n\n for (WeightedGraph.Edge e : graph.neighbors(u)) {\n int v = e.to();\n if (dist[u] + e.weight() < dist[v]) {\n dist[v] = dist[u] + e.weight();\n pred[v] = u;\n cycleVertex = v;\n }\n }\n }\n }\n\n if (cycleVertex == -1) {\n return null; // No negative cycle\n }\n\n // Go back n steps to ensure we're in the cycle\n for (int i = 0; i < n; i++) {\n cycleVertex = pred[cycleVertex];\n }\n\n // Collect cycle vertices\n List cycle = new ArrayList<>();\n int v = cycleVertex;\n do {\n cycle.add(v);\n v = pred[v];\n } while (v != cycleVertex);\n cycle.add(cycleVertex);\n\n Collections.reverse(cycle);\n return cycle;\n }\n\n static class NegativeCycleException extends Exception {\n NegativeCycleException(String message) { super(message); }\n }\n}\n```\n\n### Why Bellman-Ford Works\n\n```text\nBELLMAN-FORD INTUITION\n━━━━━━━━━━━━━━━━━━━━━━\n\nAfter k iterations:\n dist[v] = shortest path using ≤ k edges\n\nShortest path in graph with V vertices has at most V-1 edges\n(otherwise it would have a cycle).\n\nSo after V-1 iterations, all shortest paths are found.\n\nIf V-th iteration still improves some distance:\n → Path with V edges is shorter than path with V-1 edges\n → That path must have a cycle\n → That cycle must be negative (otherwise not shorter)\n → Negative cycle detected!\n```\n\n---\n\n## 🔬 Deep Dive: Floyd-Warshall Algorithm\n\n### All-Pairs Shortest Paths\n\n```java\npublic class FloydWarshall {\n private static final int INF = Integer.MAX_VALUE / 2; // Avoid overflow\n\n /**\n * Floyd-Warshall all-pairs shortest paths.\n *\n * Time: O(V³)\n * Space: O(V²)\n *\n * @return distance matrix where dist[i][j] = shortest path i→j\n */\n public static int[][] allPairsShortestPaths(int[][] graph) {\n int n = graph.length;\n int[][] dist = new int[n][n];\n\n // Initialize with direct edges\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n if (i == j) {\n dist[i][j] = 0;\n } else if (graph[i][j] != 0) {\n dist[i][j] = graph[i][j];\n } else {\n dist[i][j] = INF;\n }\n }\n }\n\n // DP: consider each vertex as intermediate\n for (int k = 0; k < n; k++) {\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n if (dist[i][k] + dist[k][j] < dist[i][j]) {\n dist[i][j] = dist[i][k] + dist[k][j];\n }\n }\n }\n }\n\n return dist;\n }\n\n /**\n * Floyd-Warshall with path reconstruction.\n */\n public static Result allPairsWithPaths(int[][] graph) {\n int n = graph.length;\n int[][] dist = new int[n][n];\n int[][] next = new int[n][n]; // next[i][j] = next vertex on path i→j\n\n // Initialize\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n if (i == j) {\n dist[i][j] = 0;\n next[i][j] = j;\n } else if (graph[i][j] != 0) {\n dist[i][j] = graph[i][j];\n next[i][j] = j;\n } else {\n dist[i][j] = INF;\n next[i][j] = -1;\n }\n }\n }\n\n // DP\n for (int k = 0; k < n; k++) {\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n if (dist[i][k] + dist[k][j] < dist[i][j]) {\n dist[i][j] = dist[i][k] + dist[k][j];\n next[i][j] = next[i][k];\n }\n }\n }\n }\n\n return new Result(dist, next);\n }\n\n public static List reconstructPath(int[][] next, int u, int v) {\n if (next[u][v] == -1) {\n return Collections.emptyList(); // No path\n }\n\n List path = new ArrayList<>();\n path.add(u);\n\n while (u != v) {\n u = next[u][v];\n path.add(u);\n }\n\n return path;\n }\n\n /**\n * Detect negative cycle using Floyd-Warshall.\n * After algorithm, if dist[i][i] < 0 for any i, negative cycle exists.\n */\n public static boolean hasNegativeCycle(int[][] dist) {\n for (int i = 0; i < dist.length; i++) {\n if (dist[i][i] < 0) {\n return true;\n }\n }\n return false;\n }\n\n public record Result(int[][] dist, int[][] next) {}\n}\n```\n\n### Floyd-Warshall DP Insight\n\n```text\nFLOYD-WARSHALL DP FORMULATION\n━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\n\nDefine: dist[k][i][j] = shortest path from i to j\n using only vertices {0, 1, ..., k-1} as intermediates\n\nBase case: dist[0][i][j] = direct edge weight (or ∞)\n\nRecurrence:\n dist[k][i][j] = min(\n dist[k-1][i][j], // Don't use vertex k\n dist[k-1][i][k] + dist[k-1][k][j] // Use vertex k\n )\n\nSpace optimization: Since we only need k-1 to compute k,\nwe can use 2D array and update in-place.\n\n for k = 0 to V-1:\n for i = 0 to V-1:\n for j = 0 to V-1:\n dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])\n```\n\n---\n\n## 🔬 Deep Dive: A* Search Algorithm\n\n### The Heuristic Advantage\n\nA* uses a heuristic function h(v) to estimate distance from v to goal, prioritizing vertices that seem closer to the goal.\n\n```java\npublic class AStar {\n /**\n * A* shortest path with heuristic.\n *\n * Time: O(E) best case (straight path), O(V²) worst case\n * Space: O(V)\n *\n * @param heuristic h(v) = estimated distance from v to target\n * Must be admissible: h(v) ≤ actual distance\n */\n public static List findPath(\n WeightedGraph graph,\n int source,\n int target,\n ToIntFunction heuristic) {\n\n int n = graph.getVertices();\n int[] gScore = new int[n]; // Actual distance from source\n int[] fScore = new int[n]; // gScore + heuristic\n int[] pred = new int[n];\n Arrays.fill(gScore, Integer.MAX_VALUE);\n Arrays.fill(fScore, Integer.MAX_VALUE);\n Arrays.fill(pred, -1);\n\n gScore[source] = 0;\n fScore[source] = heuristic.applyAsInt(source);\n\n // Priority queue ordered by f-score\n PriorityQueue openSet = new PriorityQueue<>(\n Comparator.comparingInt(a -> a[1])\n );\n openSet.offer(new int[]{source, fScore[source]});\n\n Set closedSet = new HashSet<>();\n\n while (!openSet.isEmpty()) {\n int[] curr = openSet.poll();\n int u = curr[0];\n\n if (u == target) {\n return reconstructPath(pred, source, target);\n }\n\n if (closedSet.contains(u)) continue;\n closedSet.add(u);\n\n for (WeightedGraph.Edge e : graph.neighbors(u)) {\n int v = e.to();\n if (closedSet.contains(v)) continue;\n\n int tentativeG = gScore[u] + e.weight();\n\n if (tentativeG < gScore[v]) {\n pred[v] = u;\n gScore[v] = tentativeG;\n fScore[v] = tentativeG + heuristic.applyAsInt(v);\n openSet.offer(new int[]{v, fScore[v]});\n }\n }\n }\n\n return Collections.emptyList(); // No path found\n }\n\n private static List reconstructPath(int[] pred, int source, int target) {\n List path = new ArrayList<>();\n int curr = target;\n while (curr != -1) {\n path.add(curr);\n curr = pred[curr];\n }\n Collections.reverse(path);\n return path;\n }\n}\n```\n\n### Common Heuristics\n\n```java\npublic class Heuristics {\n /**\n * Manhattan distance for grid-based pathfinding.\n * Admissible when only 4-directional movement allowed.\n */\n public static int manhattan(int x1, int y1, int x2, int y2) {\n return Math.abs(x1 - x2) + Math.abs(y1 - y2);\n }\n\n /**\n * Euclidean distance.\n * Admissible for any movement.\n */\n public static double euclidean(double x1, double y1, double x2, double y2) {\n return Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));\n }\n\n /**\n * Chebyshev distance (diagonal movement costs 1).\n * Admissible for 8-directional movement with equal diagonal cost.\n */\n public static int chebyshev(int x1, int y1, int x2, int y2) {\n return Math.max(Math.abs(x1 - x2), Math.abs(y1 - y2));\n }\n\n /**\n * Octile distance (diagonal movement costs √2).\n * More accurate for 8-directional grid movement.\n */\n public static double octile(int x1, int y1, int x2, int y2) {\n int dx = Math.abs(x1 - x2);\n int dy = Math.abs(y1 - y2);\n return Math.max(dx, dy) + (Math.sqrt(2) - 1) * Math.min(dx, dy);\n }\n}\n```\n\n### A* vs Dijkstra Visualization\n\n```text\nA* VS DIJKSTRA ON GRID\n━━━━━━━━━━━━━━━━━━━━━━\n\nGrid: S = Start, T = Target, # = Obstacle\n . = Not explored, * = Explored, P = Path\n\nDijkstra (explores uniformly): A* (explores toward target):\n\n . . . . . T . . . . . T\n . . . . . . . . . . P .\n . . # # . . . . # # P .\n . * * # . . . . . # P .\n * * * # . . . . . # P .\n S * * * . . S P P P . .\n\nDijkstra: Explores 15 cells A*: Explores 8 cells\nBoth find same shortest path, but A* explores fewer nodes!\n```\n\n---\n\n## 🔬 Deep Dive: Bidirectional Search\n\n### Meeting in the Middle\n\n```java\npublic class BidirectionalDijkstra {\n /**\n * Bidirectional Dijkstra - search from both ends.\n *\n * Time: O((V + E) log V) but explores ~half the nodes\n * Space: O(V)\n */\n public static int shortestPath(WeightedGraph graph,\n WeightedGraph reverseGraph,\n int source, int target) {\n if (source == target) return 0;\n\n int n = graph.getVertices();\n\n // Forward search from source\n int[] distF = new int[n];\n Arrays.fill(distF, Integer.MAX_VALUE);\n distF[source] = 0;\n PriorityQueue pqF = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));\n pqF.offer(new int[]{source, 0});\n boolean[] processedF = new boolean[n];\n\n // Backward search from target\n int[] distB = new int[n];\n Arrays.fill(distB, Integer.MAX_VALUE);\n distB[target] = 0;\n PriorityQueue pqB = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));\n pqB.offer(new int[]{target, 0});\n boolean[] processedB = new boolean[n];\n\n int best = Integer.MAX_VALUE;\n\n while (!pqF.isEmpty() && !pqB.isEmpty()) {\n // Alternate between forward and backward\n if (!pqF.isEmpty()) {\n int[] curr = pqF.poll();\n int u = curr[0], d = curr[1];\n\n if (d > distF[u]) continue;\n processedF[u] = true;\n\n // Check if we've met\n if (processedB[u]) {\n best = Math.min(best, distF[u] + distB[u]);\n }\n\n // Early termination\n if (d >= best) return best;\n\n for (WeightedGraph.Edge e : graph.neighbors(u)) {\n int v = e.to();\n int newDist = distF[u] + e.weight();\n if (newDist < distF[v]) {\n distF[v] = newDist;\n pqF.offer(new int[]{v, newDist});\n }\n }\n }\n\n // Similar for backward search\n if (!pqB.isEmpty()) {\n int[] curr = pqB.poll();\n int u = curr[0], d = curr[1];\n\n if (d > distB[u]) continue;\n processedB[u] = true;\n\n if (processedF[u]) {\n best = Math.min(best, distF[u] + distB[u]);\n }\n\n if (d >= best) return best;\n\n for (WeightedGraph.Edge e : reverseGraph.neighbors(u)) {\n int v = e.to();\n int newDist = distB[u] + e.weight();\n if (newDist < distB[v]) {\n distB[v] = newDist;\n pqB.offer(new int[]{v, newDist});\n }\n }\n }\n }\n\n return best == Integer.MAX_VALUE ? -1 : best;\n }\n}\n```\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Using Dijkstra with Negative Weights\n\n```java\n// ❌ Dijkstra gives WRONG answer with negative weights\nint[] dist = dijkstra(graphWithNegativeEdges, source);\n// May return incorrect distances!\n\n// ✅ Use Bellman-Ford or check for negative edges first\nif (hasNegativeEdges(graph)) {\n return bellmanFord(graph, source);\n} else {\n return dijkstra(graph, source);\n}\n```\n\n### Mistake 2: Integer Overflow in Distance Calculation\n\n```java\n// ❌ Overflow when adding to MAX_VALUE\nif (dist[u] + weight < dist[v]) { // MAX_VALUE + anything overflows!\n dist[v] = dist[u] + weight;\n}\n\n// ✅ Check for MAX_VALUE first\nif (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {\n dist[v] = dist[u] + weight;\n}\n\n// ✅ Or use long for calculations\nlong newDist = (long) dist[u] + weight;\nif (newDist < dist[v]) {\n dist[v] = (int) newDist;\n}\n```\n\n### Mistake 3: Not Handling Disconnected Vertices\n\n```java\n// ❌ Assuming all vertices are reachable\nint shortestTo5 = dist[5]; // Might be MAX_VALUE!\nSystem.out.println(\"Distance: \" + shortestTo5);\n\n// ✅ Check for unreachable\nif (dist[5] == Integer.MAX_VALUE) {\n System.out.println(\"Vertex 5 is unreachable\");\n} else {\n System.out.println(\"Distance: \" + dist[5]);\n}\n```\n\n### Mistake 4: Wrong Heuristic in A*\n\n```java\n// ❌ Inadmissible heuristic (overestimates)\nint heuristic(int v) {\n return actualDistance(v, target) * 2; // Overestimates!\n}\n// A* may not find optimal path!\n\n// ✅ Admissible heuristic (never overestimates)\nint heuristic(int v) {\n return manhattanDistance(v, target); // Always ≤ actual distance\n}\n```\n\n---\n\n## 🐛 Debug This: The Broken Shortest Path\n\nThese implementations have bugs. Find and fix them:\n\n```java\npublic class BrokenShortestPath {\n\n // Bug 1: Dijkstra\n public int[] dijkstra(int[][] graph, int src) {\n int n = graph.length;\n int[] dist = new int[n];\n boolean[] visited = new boolean[n];\n\n for (int i = 0; i < n; i++) {\n dist[i] = graph[src][i]; // Bug\n }\n\n visited[src] = true;\n\n for (int count = 0; count < n - 1; count++) {\n int u = minDistance(dist, visited);\n visited[u] = true;\n\n for (int v = 0; v < n; v++) {\n if (!visited[v] && graph[u][v] != 0) {\n dist[v] = Math.min(dist[v], dist[u] + graph[u][v]); // Bug\n }\n }\n }\n return dist;\n }\n\n // Bug 2: Bellman-Ford negative cycle detection\n public boolean hasNegativeCycle(List edges, int n, int src) {\n int[] dist = new int[n];\n Arrays.fill(dist, Integer.MAX_VALUE);\n dist[src] = 0;\n\n for (int i = 0; i < n; i++) { // Bug\n for (int[] edge : edges) {\n int u = edge[0], v = edge[1], w = edge[2];\n if (dist[u] + w < dist[v]) {\n dist[v] = dist[u] + w;\n }\n }\n }\n\n return false; // Bug: missing check\n }\n\n // Bug 3: A* heuristic usage\n public int aStar(int[][] grid, int[] start, int[] end) {\n PriorityQueue pq = new PriorityQueue<>(\n (a, b) -> a[2] - b[2] // Sort by g-score only - Bug!\n );\n // ... rest of implementation\n return -1;\n }\n\n private int minDistance(int[] dist, boolean[] visited) {\n int min = Integer.MAX_VALUE, minIdx = -1;\n for (int i = 0; i < dist.length; i++) {\n if (!visited[i] && dist[i] < min) {\n min = dist[i];\n minIdx = i;\n }\n }\n return minIdx;\n }\n}\n```\n\n

💡 Hint

\n\nLook for:\n1. Initialization of distances\n2. Loop count in Bellman-Ford\n3. Missing negative cycle check\n4. A* should sort by f-score (g + h), not just g-score\n\n

\n\n

✅ Solution

\n\n```java\npublic class FixedShortestPath {\n\n // ✅ Fix 1: Dijkstra with proper initialization\n public int[] dijkstra(int[][] graph, int src) {\n int n = graph.length;\n int[] dist = new int[n];\n boolean[] visited = new boolean[n];\n\n // ✅ Initialize all to MAX_VALUE, source to 0\n Arrays.fill(dist, Integer.MAX_VALUE);\n dist[src] = 0;\n\n for (int count = 0; count < n; count++) { // ✅ n iterations, not n-1\n int u = minDistance(dist, visited);\n if (u == -1) break; // ✅ Handle disconnected graph\n\n visited[u] = true;\n\n for (int v = 0; v < n; v++) {\n if (!visited[v] && graph[u][v] != 0\n && dist[u] != Integer.MAX_VALUE) { // ✅ Check overflow\n dist[v] = Math.min(dist[v], dist[u] + graph[u][v]);\n }\n }\n }\n return dist;\n }\n\n // ✅ Fix 2: Bellman-Ford with proper cycle detection\n public boolean hasNegativeCycle(List edges, int n, int src) {\n int[] dist = new int[n];\n Arrays.fill(dist, Integer.MAX_VALUE);\n dist[src] = 0;\n\n // ✅ V-1 iterations for relaxation\n for (int i = 0; i < n - 1; i++) {\n for (int[] edge : edges) {\n int u = edge[0], v = edge[1], w = edge[2];\n if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {\n dist[v] = dist[u] + w;\n }\n }\n }\n\n // ✅ V-th iteration to detect negative cycle\n for (int[] edge : edges) {\n int u = edge[0], v = edge[1], w = edge[2];\n if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {\n return true; // ✅ Negative cycle exists\n }\n }\n\n return false;\n }\n\n // ✅ Fix 3: A* with f-score sorting\n public int aStar(int[][] grid, int[] start, int[] end) {\n // ✅ Sort by f-score = g-score + h-score\n PriorityQueue pq = new PriorityQueue<>(\n (a, b) -> (a[2] + heuristic(a, end)) - (b[2] + heuristic(b, end))\n );\n // Or store f-score explicitly:\n // PriorityQueue pq = new PriorityQueue<>((a, b) -> a[3] - b[3]);\n // where a[3] = f-score\n\n // ... rest of implementation\n return -1;\n }\n\n private int heuristic(int[] pos, int[] end) {\n return Math.abs(pos[0] - end[0]) + Math.abs(pos[1] - end[1]);\n }\n\n private int minDistance(int[] dist, boolean[] visited) {\n int min = Integer.MAX_VALUE, minIdx = -1;\n for (int i = 0; i < dist.length; i++) {\n if (!visited[i] && dist[i] < min) {\n min = dist[i];\n minIdx = i;\n }\n }\n return minIdx;\n }\n}\n```\n\n**Bugs explained:**\n\n1. **Dijkstra initialization**: `dist[i] = graph[src][i]` only works if all vertices have direct edges from source. Should initialize to MAX_VALUE and start with source at 0.\n\n2. **Bellman-Ford iterations**: Should be V-1 iterations for relaxation, then one more iteration to detect negative cycles. Original had V iterations and no cycle check.\n\n3. **A* sorting**: A* must sort by f-score (g + h), not just g-score. Sorting by g-score alone makes it equivalent to Dijkstra, losing the heuristic benefit.\n\n

\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: Network Delay Time (LeetCode 743) ⭐⭐\n\nFind time for signal to reach all nodes from source.\n\n```java\npublic class NetworkDelay {\n /**\n * @param times Array of [source, target, time]\n * @param n Number of nodes (1 to n)\n * @param k Source node\n * @return Time for all nodes to receive signal, or -1 if impossible\n */\n public int networkDelayTime(int[][] times, int n, int k) {\n // Your implementation using Dijkstra\n }\n}\n```\n\n---\n\n### Exercise 2: Cheapest Flights Within K Stops (LeetCode 787) ⭐⭐⭐\n\nFind cheapest flight with at most K stops.\n\n```java\npublic class CheapestFlight {\n /**\n * @param flights Array of [from, to, price]\n * @param src Source city\n * @param dst Destination city\n * @param k Maximum stops allowed\n * @return Cheapest price, or -1 if no route\n */\n public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {\n // Your implementation (modified Bellman-Ford or BFS)\n }\n}\n```\n\n

💡 Hint

\n\nUse Bellman-Ford with exactly k+1 iterations (k stops = k+1 edges). Or use BFS with level tracking.\n\n

\n\n---\n\n### Exercise 3: Path with Maximum Probability (LeetCode 1514) ⭐⭐⭐\n\nFind path with highest probability of success.\n\n```java\npublic class MaxProbability {\n /**\n * @param edges Undirected edges\n * @param succProb Probability of each edge\n * @return Maximum probability from start to end\n */\n public double maxProbability(int n, int[][] edges, double[] succProb,\n int start, int end) {\n // Your implementation (modified Dijkstra - maximize instead of minimize)\n }\n}\n```\n\n---\n\n### Exercise 4: Shortest Path in Grid with Obstacles (LeetCode 1293) ⭐⭐⭐⭐\n\nFind shortest path in grid where you can eliminate up to k obstacles.\n\n```java\npublic class ShortestPathWithObstacles {\n /**\n * @param grid 0 = empty, 1 = obstacle\n * @param k Maximum obstacles you can eliminate\n * @return Shortest path length, or -1 if impossible\n */\n public int shortestPath(int[][] grid, int k) {\n // Your implementation (BFS with state = (x, y, remainingK))\n }\n}\n```\n\n---\n\n### Exercise 5: Find Negative Cycle ⭐⭐⭐⭐\n\nReturn the actual vertices forming a negative cycle.\n\n```java\npublic class NegativeCycleFinder {\n /**\n * Find and return vertices in a negative cycle.\n * @return List of vertices forming cycle, or null if no cycle\n */\n public List findNegativeCycle(WeightedGraph graph) {\n // Your implementation\n }\n}\n```\n\n---\n\n## 🎤 Interview Questions\n\n### Question 1: When would you use each shortest path algorithm?\n\n**Answer:**\n\n| Algorithm | Use When |\n|-----------|----------|\n| **BFS** | Unweighted graph, need shortest by edge count |\n| **Dijkstra** | Weighted, non-negative, single source |\n| **A*** | Single source-target with good heuristic |\n| **Bellman-Ford** | Has negative weights, need cycle detection |\n| **Floyd-Warshall** | Need all-pairs, dense graph, V is small |\n\n**Decision factors:**\n1. Negative weights? → Bellman-Ford or Floyd-Warshall\n2. Single source or all pairs?\n3. Graph density (E vs V²)?\n4. Have good heuristic? → Consider A*\n\n---\n\n### Question 2: Why doesn't Dijkstra work with negative weights?\n\n**Answer:**\n\nDijkstra's greedy approach assumes: \"Once a vertex is processed, its distance is final.\"\n\nWith negative weights, this assumption breaks:\n\n```text\n A ──(5)──→ B\n │ │\n (1) (-3)\n ↓ ↓\n C ────────→ D\n\nDijkstra from A:\n1. Process A: dist[B]=5, dist[C]=1\n2. Process C (smallest unprocessed): dist[C]=1 marked final\n3. Process B: could update D via B\n4. But C→B→D might be shorter than C's \"final\" distance!\n\nPath A→C→? = 1+?\nPath A→B→D = 5+(-3) = 2\nIf C→D exists with weight 4: A→C→D = 5 (worse than A→B→D = 2)\n\nThe problem: Processing C early misses the shorter path through B.\n```\n\n---\n\n### Question 3: Explain the A* heuristic requirements\n\n**Answer:**\n\nA* requires an **admissible** heuristic: h(v) ≤ actual distance from v to goal.\n\n**Why admissibility matters:**\n- If h overestimates, A* might skip the optimal path\n- Admissible h guarantees optimal solution\n\n**Consistency/Monotonicity** (stronger): h(u) ≤ cost(u,v) + h(v)\n- Guarantees A* won't revisit nodes\n- All consistent heuristics are admissible\n\n**Common heuristics:**\n- **Manhattan**: |dx| + |dy| - admissible for 4-direction grid\n- **Euclidean**: √(dx² + dy²) - admissible for any movement\n- **Zero**: h(v) = 0 - always admissible, but A* becomes Dijkstra\n\n**Trade-off**: Higher h (closer to actual) → fewer nodes explored, but more computation per node.\n\n---\n\n### Question 4: How would you detect a negative cycle?\n\n**Answer:**\n\n**Method 1: Bellman-Ford extra iteration**\n```java\n// After V-1 relaxation iterations\nfor (each edge (u,v,w)) {\n if (dist[u] + w < dist[v]) {\n return true; // Negative cycle exists\n }\n}\n```\n\n**Method 2: Floyd-Warshall diagonal check**\n```java\n// After algorithm completes\nfor (int i = 0; i < n; i++) {\n if (dist[i][i] < 0) {\n return true; // Negative cycle exists\n }\n}\n```\n\n**Method 3: DFS with path tracking**\n- Track sum of edge weights on current DFS path\n- If we return to a vertex with lower total weight, negative cycle found\n\n**Finding the actual cycle:**\n- Run Bellman-Ford V iterations (not V-1)\n- Any vertex updated in V-th iteration is reachable from negative cycle\n- Trace back through predecessors to find cycle\n\n---\n\n### Question 5: Compare single-source algorithms complexity\n\n**Answer:**\n\n| Algorithm | Time | Space | Notes |\n|-----------|------|-------|-------|\n| BFS | O(V+E) | O(V) | Unweighted only |\n| Dijkstra (binary heap) | O((V+E) log V) | O(V) | No negative weights |\n| Dijkstra (Fibonacci heap) | O(E + V log V) | O(V) | Better for dense graphs |\n| Bellman-Ford | O(VE) | O(V) | Handles negative weights |\n| SPFA | O(VE) worst, O(E) avg | O(V) | Optimized Bellman-Ford |\n\n**Practical guidance:**\n- Sparse graph (E ≈ V): Dijkstra with binary heap\n- Dense graph (E ≈ V²): Dijkstra or Bellman-Ford similar\n- Need negative weights: Bellman-Ford\n- Unweighted: Always use BFS\n\n---\n\n## 📋 Quick Reference\n\n### Algorithm Comparison\n\n| | Dijkstra | Bellman-Ford | Floyd-Warshall | A* |\n|-|----------|--------------|----------------|-----|\n| **Type** | Greedy | DP | DP | Heuristic |\n| **Negative edges** | No | Yes | Yes | No |\n| **Negative cycles** | No | Detects | Detects | No |\n| **Single source** | Yes | Yes | No (all pairs) | Yes |\n| **Time** | O((V+E)log V) | O(VE) | O(V³) | O(E) to O(V²) |\n\n### Code Templates\n\n```java\n// Dijkstra Template\nint[] dijkstra(Graph g, int src) {\n int[] dist = new int[n];\n Arrays.fill(dist, INF);\n dist[src] = 0;\n PriorityQueue pq = new PriorityQueue<>((a,b) -> a[1] - b[1]);\n pq.offer(new int[]{src, 0});\n\n while (!pq.isEmpty()) {\n int[] curr = pq.poll();\n int u = curr[0], d = curr[1];\n if (d > dist[u]) continue;\n\n for (Edge e : g.neighbors(u)) {\n if (dist[u] + e.weight < dist[e.to]) {\n dist[e.to] = dist[u] + e.weight;\n pq.offer(new int[]{e.to, dist[e.to]});\n }\n }\n }\n return dist;\n}\n\n// Bellman-Ford Template\nint[] bellmanFord(Graph g, int src) {\n int[] dist = new int[n];\n Arrays.fill(dist, INF);\n dist[src] = 0;\n\n for (int i = 0; i < n - 1; i++) {\n for (Edge e : allEdges) {\n if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {\n dist[e.to] = dist[e.from] + e.weight;\n }\n }\n }\n // Check negative cycle...\n return dist;\n}\n\n// Floyd-Warshall Template\nint[][] floydWarshall(int[][] graph) {\n int[][] dist = copy(graph);\n for (int k = 0; k < n; k++)\n for (int i = 0; i < n; i++)\n for (int j = 0; j < n; j++)\n dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);\n return dist;\n}\n```\n\n---\n\n## 📅 Review Schedule\n\n| Day | Focus | Time |\n|-----|-------|------|\n| Day 1 | Read article, implement Dijkstra | 60 min |\n| Day 3 | Implement Bellman-Ford with cycle detection | 30 min |\n| Day 7 | Implement A* for grid pathfinding | 30 min |\n| Day 14 | Solve LeetCode shortest path problems | 45 min |\n| Day 30 | Review and compare algorithm trade-offs | 20 min |\n\n---\n\n## 🔗 What's Next?\n\n**Part 13: Minimum Spanning Tree** covers:\n- Union-Find data structure\n- Kruskal's algorithm\n- Prim's algorithm\n- Borůvka's algorithm\n- MST applications\n\n**Key insight preview**: MST asks \"connect all vertices with minimum total edge weight\" - different from shortest path which asks about paths between specific vertices.\n\n---\n\n*This article is part of the Algorithms Compendium series. For the complete learning path, see Part 0: How to Use This Series.*\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.180428Z","createdAt","2026-06-10T07:19:25.181273Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",25,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",2,"seriesOrder",12,"author",{"_31":55,"_103":57,"_104":105,"_106":107,"_108":-5,"_109":-5,"_110":-5,"_111":-5,"_112":-5},"category",{"_31":99,"_73":59,"_35":100,"_76":101,"_102":-5},"tags",[79,80,81,82,83],"series",{"_31":62,"_73":74,"_35":75,"_76":77,"_78":23},"name","Algorithms Compendium: From Theory to Production","algorithms-compendium","description","A comprehensive 23-part series covering all essential algorithms for Java developers. From foundational concepts like complexity analysis and recursion, through sorting (QuickSort, MergeSort, TimSort), searching (binary search, string matching), graph algorithms (DFS, BFS, Dijkstra, MST), dynamic programming, greedy algorithms, backtracking, to probabilistic data structures (Bloom filters, HyperLogLog) and interview patterns. Includes real production stories, mental models, exercises, and 100+ interview questions.","isActive",{"_31":96,"_73":97,"_35":98},{"_31":93,"_73":94,"_35":95},{"_31":90,"_73":91,"_35":92},{"_31":87,"_73":88,"_35":89},{"_31":84,"_73":85,"_35":86},169,"Shortest Path","shortest-path",167,"Floyd-warshall","floyd-warshall",165,"Dijkstra","dijkstra",166,"Bellman-ford","bellman-ford",168,"A*","a*",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]