Apr 13, 2025

Shortest Path Algorithms

Overview

Choose a shortest-path algorithm from the graph’s edge weights and whether the problem asks for one source or all pairs:

Algorithm	Use it when	Time	Space
BFS	The graph is unweighted, or every edge has the same weight	`O(V + E)`	`O(V)`
Dijkstra	Edge weights are nonnegative	`O((V + E) log V)` with a min-heap	`O(V + E)`
Bellman-Ford	Negative edge weights may exist	`O(VE)`	`O(V)`
Floyd-Warshall	All-pairs shortest paths are needed and the graph is small	`O(V³)`	`O(V²)`

BFS is covered in the breadth-first search post, so this post focuses on the other three algorithms. Dijkstra cannot safely finalize distances when negative edges exist. Bellman-Ford can detect a reachable negative cycle with one extra relaxation pass. Floyd-Warshall supports negative edges, but shortest paths are undefined when a negative cycle is usable.

For Dijkstra, define the state before writing the algorithm. The state is normally just node, but constraints may expand it to (node, flightsUsed) or (node, discountsUsed). The distance table and heap must store the entire state. These expanded problems use the same algorithm, but their complexity depends on the number of expanded states and transitions rather than only the original V and E.

Templates

Dijkstra

Define the complete state. Use one best distance per node normally, or a 2D table when a resource such as flights or discounts is part of the state.
Set the starting state’s cost to zero and add it to the min-heap.
Pop the cheapest state. Skip it only when cost > best[state]; using >= would incorrectly skip its current best entry.
Compute the transition cost. Ordinary shortest paths use cost + weight; minimax paths such as 1631 use max(cost, weight).
Store and push a neighbor only when newCost < best[nextState].
With nonnegative transitions, the first non-stale destination state removed from the heap is optimal.

import java.util.*;

class Dijkstra {
    public Map<Integer, Integer> shortestPaths(Map<Integer, List<int[]>> adjList, int source) {
        Map<Integer, Integer> best = new HashMap<>();
        best.put(source, 0);
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        minHeap.offer(new int[]{0, source}); // cost, node

        while (!minHeap.isEmpty()) {
            int[] curr = minHeap.poll();
            int cost = curr[0], node = curr[1];
            if (cost > best.getOrDefault(node, Integer.MAX_VALUE)) continue;

            for (int[] edge : adjList.getOrDefault(node, new ArrayList<>())) {
                int nei = edge[0], weight = edge[1];
                int newCost = cost + weight;
                if (newCost < best.getOrDefault(nei, Integer.MAX_VALUE)) {
                    best.put(nei, newCost);
                    minHeap.offer(new int[]{newCost, nei});
                }
            }
        }
        return best;
    }
}

import heapq

def dijkstra(graph, source):
    best = {source: 0}
    min_heap = [(0, source)]

    while min_heap:
        cost, node = heapq.heappop(min_heap)
        if cost > best.get(node, float('inf')):
            continue
        for nei, weight in graph[node]:
            new_cost = cost + weight
            if new_cost < best.get(nei, float('inf')):
                best[nei] = new_cost
                heapq.heappush(min_heap, (new_cost, nei))

    return best

Bellman-Ford

Relax every edge up to V - 1 times; after round i, paths using at most i edges are known.
Stop early if a complete round makes no changes.
If an edge can still be relaxed afterward, a reachable negative cycle exists.

import java.util.Arrays;

class BellmanFord {
	public long[] shortestPaths(int n, int[][] edges, int source) {
		long infinity = Long.MAX_VALUE / 4;
		long[] dist = new long[n];
		Arrays.fill(dist, infinity);
		dist[source] = 0;

		for (int i = 0; i < n - 1; i++) {
			boolean changed = false;
			for (int[] edge : edges) {
				int u = edge[0], v = edge[1], weight = edge[2];
				if (dist[u] != infinity && dist[u] + weight < dist[v]) {
					dist[v] = dist[u] + weight;
					changed = true;
				}
			}
			if (!changed) break;
		}

		for (int[] edge : edges)
			if (dist[edge[0]] != infinity && dist[edge[0]] + edge[2] < dist[edge[1]]) return null;
		return dist;
	}
}

def bellman_ford(n, edges, source):
    dist = [float("inf")] * n
    dist[source] = 0

    for _ in range(n - 1):
        changed = False
        for u, v, weight in edges:
            if dist[u] != float("inf") and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                changed = True
        if not changed:
            break

    for u, v, weight in edges:
        if dist[u] != float("inf") and dist[u] + weight < dist[v]:
            return None
    return dist

Floyd-Warshall

Initialize a distance matrix with zero on the diagonal and direct-edge weights elsewhere.
For an undirected graph, store each direct edge in both directions.
For each intermediate node k, try every route i -> k -> j.
A negative diagonal value after processing indicates a negative cycle.

import java.util.Arrays;

class FloydWarshall {
	public long[][] shortestPaths(int n, int[][] edges) {
		long infinity = Long.MAX_VALUE / 4;
		long[][] dist = new long[n][n];
		for (int i = 0; i < n; i++) {
			Arrays.fill(dist[i], infinity);
			dist[i][i] = 0;
		}
		for (int[] edge : edges)
			dist[edge[0]][edge[1]] = Math.min(dist[edge[0]][edge[1]], edge[2]);

		for (int k = 0; k < n; k++)
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++)
					if (dist[i][k] != infinity && dist[k][j] != infinity)
						dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
		return dist;
	}
}

def floyd_warshall(n, edges):
    dist = [[float("inf")] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, weight in edges:
        dist[u][v] = min(dist[u][v], weight)

    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

Problems

743. Network Delay Time

Find how long a signal from one node takes to reach every node in a directed graph with positive travel times. Dijkstra computes the earliest arrival at each node; the maximum finite distance is the total delay.

import java.util.*;

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        Map<Integer, List<int[]>> adjList = new HashMap<>();

        for (int[] time : times){
            int u = time[0], v = time[1], w = time[2];
            adjList.computeIfAbsent(u, ignored -> new ArrayList<>()).add(new int[]{v, w});
        }

        Map<Integer, Integer> nodeToTime = new HashMap<>();
        nodeToTime.put(k, 0);
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        minHeap.offer(new int[]{0, k}); //time, node

        while (!minHeap.isEmpty()){
            int[] curr = minHeap.poll();
            int dist = curr[0], node = curr[1];

            if (dist > nodeToTime.getOrDefault(node, Integer.MAX_VALUE)){
                continue;
            }
            for (int[] pair : adjList.getOrDefault(node, new ArrayList<>())){
                int newNode = pair[0], weight = pair[1];
                int newDist = dist + weight;
                if (newDist < nodeToTime.getOrDefault(newNode, Integer.MAX_VALUE)){
                    nodeToTime.put(newNode, newDist);
                    minHeap.offer(new int[]{newDist, newNode});
                }
            }
        }
        if (nodeToTime.size() == n){
            return Collections.max(nodeToTime.values());
        } else {
            return -1;
        } 
    }
}

import collections
import heapq
from typing import List

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        # Time complexity: O((V+E)logV) Space complexity: O(V+E)
        graph = collections.defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))

        # node_to_time[node] = shortest KNOWN distance from source k to node.
        # It is tentative during the algorithm, and finalized when the node is popped
        # from the heap with a non-outdated distance.
        node_to_time = {k : 0}
        # Heap entries are (distance_from_source, node).
        # distance_from_source is total path distance, not just one edge weight.
        min_heap = [(0, k)]
        while min_heap:
            # The FIRST time node is popped, dist is the MIN distance from source to node.
            dist, node = heapq.heappop(min_heap)
            # VIP: we have already stored a shorter path
            # Ignore the worse duplicate, just CONTINUE!
            # >= is INCORRECT here!
            if dist > node_to_time.get(node, float('inf')):
                continue
            for nei, weight in graph[node]:
                new_dist = dist + weight
                # <= will introduce useless duplicate work!
                if new_dist < node_to_time.get(nei, float('inf')):
                    # WHENEVER we find a smaller distance, we store it in res.
                    node_to_time[nei] = new_dist
                    heapq.heappush(min_heap, (new_dist, nei))
        return max(node_to_time.values()) if len(node_to_time) == n else -1

1631. Path With Minimum Effort

Treat each cell as a node and the absolute height difference between adjacent cells as an edge cost. A path’s effort is its largest edge cost, so Dijkstra relaxes a neighbor with max(currentEffort, heightDifference) instead of adding the edge cost.

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int minimumEffortPath(int[][] heights) {
        int R = heights.length;
        int C = heights[0].length;

        int[][] dist = new int[R][C];
        for (int[] row : dist) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        dist[0][0] = 0;
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        minHeap.offer(new int[]{0, 0, 0}); // effort, row, col
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        while (!minHeap.isEmpty()) {
            int[] curr = minHeap.poll();
            int effort = curr[0], row = curr[1], col = curr[2];

            if (effort > dist[row][col]) {
                continue;
            }

            for (int[] dir : dirs) {
                int nextR = row + dir[0];
                int nextC = col + dir[1];
                if (nextR >= 0 && nextR < R && nextC >= 0 && nextC < C) {
                    int diff = Math.abs(heights[row][col] - heights[nextR][nextC]);
                    int newEffort = Math.max(effort, diff);
                    if (newEffort < dist[nextR][nextC]) {
                        minHeap.offer(new int[]{newEffort, nextR, nextC});
                        dist[nextR][nextC] = newEffort;
                    }
                }
            }
        }

        return dist[R - 1][C - 1];
    }
}

import heapq
from typing import List

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        R, C = len(heights), len(heights[0])

        # need to keep track of efforts at each location
        dist = [[float('inf')]*C for _ in range(R)]
        dist[0][0] = 0
        min_heap = [(0, 0, 0)] # effort, row, col
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        while min_heap:
            effort, row, col = heapq.heappop(min_heap)

            if effort > dist[row][col]:
                continue

            for dr, dc in dirs:
                next_r, next_c = row + dr, col + dc
                if 0 <= next_r < R and 0 <= next_c < C:
                    diff = abs(heights[row][col]-heights[next_r][next_c])
                    new_effort = max(effort, diff)
                    if new_effort < dist[next_r][next_c]:
                        heapq.heappush(min_heap, (new_effort, next_r, next_c))
                        dist[next_r][next_c] = new_effort

        return dist[-1][-1]

787. Cheapest Flights Within K Stops

Find the cheapest route using at most k intermediate stops, meaning at most k + 1 flights. Treat (city, flightsUsed) as the Dijkstra state because reaching the same city after a different number of flights represents a different route. The first destination state removed from the min-heap has the cheapest valid cost.

import java.util.*;

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int[] flight : flights){
            int u = flight[0];
            int v = flight[1];
            int p = flight[2];
            graph.computeIfAbsent(u, key -> new ArrayList<>()).add(new int[]{v, p});
        }

        int maxFlights = 1 + k;
        int INF = 1000000000;
        int[][] costs = new int[n][1 + maxFlights];
        for (int i = 0; i < n; i++) {
            Arrays.fill(costs[i], INF);
        }
        costs[src][0] = 0; // should have it for consistency

        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        minHeap.offer(new int[]{0, src, 0}); //cost, node, flight

        while (!minHeap.isEmpty()){
            int[] curr = minHeap.poll();
            int cost = curr[0], city = curr[1], count = curr[2];
            // must be > (>= is wrong!)
            if (cost > costs[city][count]){
                continue;
            }
            if (city == dst){
                return cost;
            }
            for (int[] edge : graph.getOrDefault(city, new ArrayList<>())) {
                int newCity = edge[0];
                int price = edge[1];

                if (count < maxFlights) {
                    int newCost = cost + price;
                    int newCount = count + 1;
                    // must be < (<= introduces extra work)
                    if (newCost < costs[newCity][newCount]) {
                        costs[newCity][newCount] = newCost;
                        minHeap.offer(new int[]{newCost, newCity, newCount});
                    }
                }
            }
        }
        return -1;
    }
}

from collections import defaultdict
import heapq
from typing import List

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        graph = defaultdict(list)

        for u, v, price in flights:
            graph[u].append((v, price))

        max_flights = k + 1
        costs = [[float('inf')] * (1 + max_flights) for _ in range(n)]
        min_heap = [(0, src, 0)] # (cost_to_city, city, flights_used)

        while min_heap:
            cost, city, flights = heapq.heappop(min_heap)

            if cost > costs[city][flights]:
                continue

            if city == dst:
                return cost

            for new_city, price in graph[city]:
                if flights < max_flights:
                    new_cost = cost + price
                    new_flights = 1 + flights
                    if new_cost < costs[new_city][new_flights]:
                        costs[new_city][new_flights] = new_cost
                        heapq.heappush(min_heap, (new_cost, new_city, new_flights))

        return -1

1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

Compute all-pairs shortest distances, count how many other cities each city can reach within the threshold, and return the largest city index on ties. Floyd-Warshall tries every city as an intermediate point in O(n³) time.

import java.util.Arrays;

class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int INF = 1000000000;
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], INF);
            dist[i][i] = 0;
        }

        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            dist[u][v] = w;
            dist[v][u] = w;
        }

        // Intermediate node must be the outer loop.
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        int minCount = n;
        int res = -1;
        for (int r = 0; r < n; r++) {
            int count = 0;
            for (int c = 0; c < n; c++) {
                if (r != c && dist[r][c] <= distanceThreshold) {
                    count++;
                }
            }
            if (count <= minCount) {
                minCount = count;
                res = r;
            }
        }

        return res;
    }
}

from typing import List

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        # Initialize distance matrix with infinity
        dist = [[float('inf')] * n for _ in range(n)]
        for i in range(n):
            dist[i][i] = 0

        # Fill in direct edges (bidirectional)
        for u, v, w in edges:
            dist[u][v] = w
            dist[v][u] = w

        # Floyd-Warshall: try each vertex as intermediate
        for k in range(n):                    # intermediate node must be outer loop
            for i in range(n):                # source
                for j in range(n):            # destination
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

        # Find city with fewest reachable within threshold
        min_count = n
        res = -1

        for r in range(n):
            count = 0
            for c in range(n):
                if  r != c and dist[r][c] <= distanceThreshold:
                    count += 1

            if count <= min_count:
                min_count = count
                res = r

        return res

2093. Minimum Cost to Reach City With Discounts

Find the minimum highway cost when a limited number of tolls may be halved. Run Dijkstra over (city, discountsUsed) states. Every highway produces a full-price transition and, when available, a discounted transition.

import java.util.*;

class Solution {
    public int minimumCost(int n, int[][] highways, int discounts) {
        Map<Integer, List<int[]>> graph = new HashMap<>();

        for (int[] highway : highways) {
            int city1 = highway[0], city2 = highway[1], toll = highway[2];
            graph.computeIfAbsent(city1, key -> new ArrayList<>()).add(new int[]{city2, toll});
            graph.computeIfAbsent(city2, key -> new ArrayList<>()).add(new int[]{city1, toll});
        }

        // best[node][discountsUsed] is the best cost seen so far.
        int INF = 1000000000;
        int[][] best = new int[n][1 + discounts];
        for (int[] row : best) {
            Arrays.fill(row, INF);
        }
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        minHeap.offer(new int[]{0, 0, 0}); // costToNode, discountsUsed, node

        while (!minHeap.isEmpty()) {
            int[] curr = minHeap.poll();
            int costToNode = curr[0], discountsUsed = curr[1], node = curr[2];

            if (node == n - 1) {
                return costToNode;
            }
            if (costToNode > best[node][discountsUsed]) {
                continue;
            }

            for (int[] pair : graph.getOrDefault(node, new ArrayList<>())) {
                int nei = pair[0], toll = pair[1];
                int newCost = costToNode + toll;
                if (newCost < best[nei][discountsUsed]) {
                    best[nei][discountsUsed] = newCost;
                    minHeap.offer(new int[]{newCost, discountsUsed, nei});
                }

                if (discountsUsed + 1 <= discounts) {
                    int newCost2 = costToNode + toll / 2;
                    if (newCost2 < best[nei][1 + discountsUsed]) {
                        best[nei][1 + discountsUsed] = newCost2;
                        minHeap.offer(new int[]{newCost2, 1 + discountsUsed, nei});
                    }
                }
            }
        }

        return -1;
    }
}

from collections import defaultdict
import heapq
from typing import List

class Solution:
    def minimumCost(self, n: int, highways: List[List[int]], discounts: int) -> int:
        graph = defaultdict(list)

        for city1, city2, toll in highways:
            graph[city1].append((city2, toll))
            graph[city2].append((city1, toll))

        # best[node][discounts_used] --> best cost seen so far
        best = [[float('inf')] * (1 + discounts) for _ in range(n)]
        min_heap = [(0, 0, 0)] # (cost_to_node, discounts_used, node)

        while min_heap:
            cost_to_node, discounts_used, node = heapq.heappop(min_heap)

            if node == n - 1:
                return cost_to_node

            if cost_to_node > best[node][discounts_used]:
                continue

            for nei, toll in graph[node]:
                new_cost = cost_to_node + toll
                if new_cost < best[nei][discounts_used]:
                    best[nei][discounts_used] = new_cost
                    heapq.heappush(min_heap, (new_cost, discounts_used, nei))

                if discounts_used + 1 <= discounts:
                    new_cost2 = cost_to_node + toll//2
                    if new_cost2 < best[nei][1+discounts_used]:
                        best[nei][1+discounts_used] = new_cost2
                        heapq.heappush(min_heap, (new_cost2, 1+discounts_used, nei))

        return -1