DSA: Graph Shortest Path Algorithms

Solution to Last Week's Challenge

Last week's problem was: DSA: Backtracking Problems Demystified

The optimal solution uses dsa: backtracking problems demystified pattern with careful state management.

Complexity Analysis:

• Time Complexity: O(n)
• Space Complexity: O(1)

Graph shortest path algorithms are a cornerstone of computer science, powering everything from Google Maps to the BGP routing protocols that keep the internet functioning. In the context of technical interviews, these algorithms are frequently used to evaluate a candidate’s grasp of graph theory, greedy strategies, and dynamic programming. Mastering these patterns allows you to move beyond simple traversals and solve complex optimization problems where the goal is to minimize cost, distance, or time.

For a senior engineer, the challenge isn't just knowing the algorithms but knowing when to apply them. Choosing between a Breadth-First Search (BFS) and Dijkstra’s algorithm can be the difference between an $O(V + E)$ solution and a timeout. In real-world systems, these algorithms are often modified to handle massive datasets, dynamic edge weights, or multi-objective constraints. This post breaks down the core shortest path patterns you need to ace your next system design or coding interview.

Theory and Core Concepts

The objective of a shortest path algorithm is to find a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized. The "best" algorithm depends entirely on the graph's characteristics: weight distribution, edge directionality, and the presence of cycles.

1. Breadth-First Search (BFS): Best for unweighted graphs. It explores neighbors layer by layer, ensuring the first time a node is reached, it is via the shortest possible path.
2. Dijkstra’s Algorithm: A greedy approach for weighted graphs without negative edges. It uses a priority queue to always expand the node with the current minimum distance.
3. Bellman-Ford: A dynamic programming approach that can handle negative weights and detect negative cycles. It relaxes all edges $V-1$ times.
4. Floyd-Warshall: Used when you need the shortest path between every single pair of nodes in a graph.

Pattern Visualization

When faced with a shortest path problem, follow this decision logic to identify the optimal approach.

Implementation

Let's look at the transition from a basic BFS to an optimized Dijkstra’s implementation in Python.

1. BFS (Unweighted Shortest Path)

This is the standard approach for finding the minimum number of edges between nodes.

from collections import deque

def shortest_path_bfs(graph, start, target):
    # Time: O(V + E) | Space: O(V)
    queue = deque([(start, 0)])
    visited = {start}
    
    while queue:
        node, dist = queue.popleft()
        if node == target:
            return dist
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    return -1

2. Dijkstra’s Algorithm (Weighted Shortest Path)

When edges have weights, we use a Min-Priority Queue (heap) to track the minimum distance to each node.

import heapq

def dijkstra(graph, start, n):
    # graph: dict of {node: [(neighbor, weight)]}
    # Time: O(E log V) | Space: O(V)
    distances = {i: float('inf') for i in range(n)}
    distances[start] = 0
    pq = [(0, start)] # (distance, node)
    
    while pq:
        curr_dist, u = heapq.heappop(pq)
        
        if curr_dist > distances[u]:
            continue
            
        for v, weight in graph.get(u, []):
            if distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight
                heapq.heappush(pq, (distances[v], v))
                
    return distances

Complexity Analysis Table

Common Patterns

Multi-Source BFS

Sometimes you need to find the shortest distance from any of several starting points to all other nodes. Instead of running BFS multiple times, you push all starting points into the queue initially.

def multi_source_bfs(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    # Add all sources (e.g., all 1s in a grid)
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                queue.append((r, c, 0))
    # Standard BFS logic follows...

0-1 BFS

If weights are only 0 and 1, a full Priority Queue is overkill. Use a deque: if the weight is 0, appendleft; if 1, append. This keeps the deque sorted and runs in $O(V+E)$.

Practice Problems

The following chart maps common LeetCode-style problems by their interview frequency and relative difficulty.

This Week's Interview Challenge: The Signal Relay

Problem Statement: You are given a network of n servers, labeled from 1 to n. You are also given times, a list of travel times for a signal to move between servers directed edges times[i] = (ui, vi, wi), where ui is the source server, vi is the target server, and wi is the time it takes for a signal to travel.

We send a signal from a given server k. Return the minimum time it takes for all n servers to receive the signal. If it is impossible for all n servers to receive the signal, return -1.

Example 1:

• Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
• Output: 2

Example 2:

• Input: times = [[1,2,1]], n = 2, k = 2
• Output: -1

Constraints:

• 1 <= k <= n <= 100
• 1 <= times.length <= 6000
• 0 <= wi <= 100

Hints:

1. This is a weighted graph. Which algorithm handles single-source shortest paths most efficiently?
2. The total time for all servers to receive the signal is determined by the server that receives it last.
3. After running your algorithm, check if any server's shortest distance remains "infinity."
4. Use a min-heap to keep the complexity at $O(E \log V)$.

Template Code:

import heapq

def networkDelayTime(times, n, k):
    # TODO: Implement the shortest path logic
    pass

# Submit your solution and check back next week for the detailed answer!

Conclusion

Mastering graph shortest path algorithms is less about memorizing code and more about understanding the constraints of your data. If the edges are unweighted, BFS is your best friend. If weights are involved, Dijkstra is the industry standard. For systems where costs can be negative (like financial arbitrage), Bellman-Ford becomes essential. In interviews, always clarify the nature of the weights and the graph size before committing to an implementation.

References:

• https://algs4.cs.princeton.edu/44sp/
• https://visualgo.net/en/sssp
• https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/
• https://en.wikipedia.org/wiki/Shortest_path_problem