Choosing the Right Shortest Path Algorithm

#interview #career #algorithms #faang

Shortest path problems on LeetCode vary by constraint. Graphs can have weights, no weights, single source focuses, or all pairs requirements. Some have positive costs and others have negative costs.

Each specific situation has a corresponding algorithm. Understanding the constraints of the graph dictates the strategy.

Identifying the Graph

Before writing code, verify the terrain.

The Clear Graph

The first question is whether every step costs the same.

Calculating degrees of separation in a social network or moving between cells in a maze means the costs are uniform.
Dealing with traffic where one road takes 5 minutes and another takes 50, flight prices, or effort means each step has a unique cost. These are weighted graphs.

The Disguised Graph

Sometimes the problem hides the graph.

The Matrix: A 2D grid where each cell is a node and valid moves are edges. If moving to an adjacent cell costs 1, it is a simple BFS.
State transitions: Consider Word Ladder. Each word is a node and a one character difference is the edge. Since every transform costs 1, this is a BFS problem.
Resource management: Problems like Cheapest Flights Within K Stops are weighted graphs requiring you to track cost while adhering to state constraints.

Selection Logic

Select the algorithm based on what the graph requires.

BFS

If every step costs the same, use Breadth-First Search. The first time the search reaches a node is the shortest path.

Dijkstra

When roads have different lengths but they are all positive, use Dijkstra. A discovery at one point in the search assumes no future path through a positive weight road can make it better.

Bellman-Ford

If a path provides a negative cost, Dijkstra fails. Bellman-Ford handles negative weights and detects cycles where a path keeps getting cheaper forever.

Floyd-Warshall

If the problem requires the shortest path from every node to every other node, use Floyd-Warshall. This checks every node as a possible layover to solve for all pairs.

Escalation of Power

As graph rules become more complex, the algorithms become heavier.

BFS is fastest but cannot handle weights.
Dijkstra handles weights but requires a priority queue and fails on negative costs.
Bellman-Ford handles negatives and cycles but uses repeated loops.
Floyd-Warshall handles all pairs but uses triple nested loops.

The Brute Force Hack

You do not always need the most efficient algorithm to pass the interview. If you struggle to implement the minHeap logic for Dijkstra, use Bellman-Ford as a brute force alternative.

You do not need a priority queue. Take the core idea of edge relaxation.

Each pass through all edges discovers the shortest path using one additional edge. The first pass finds shortest paths with one edge, the second pass finds shortest paths with two edges, and so on. Since a shortest path in a graph of $V$ nodes can have at most $V-1$ edges, this ensures every node is covered. It is two nested loops and handles everything Dijkstra can.

# The brute force alternative
# n: number of nodes, edges: list of (u, v, weight)
def shortest_path_hack(n, edges, start):
    dist = [float('inf')] * n
    dist[start] = 0

    # Its just a nested loop and you could pass the in without Dijkstra.
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # No need to handle weighted and negative edges.
    # We skip this part of belman ford. Quick Win. Two Birds.
    return dist