Code Templates

Use these memorizable templates to implement shortest path algorithms efficiently. Each template is ready to adapt to most interview problems of this type. For theoretical background, check out the Concept Guide.

Dijkstra’s Algorithm - Single Source Shortest Path

Description: Finds shortest paths from a single source node to all other nodes in graphs with non-negative edge weights. This is the most commonly tested shortest path algorithm in interviews.

/**
 * Dijkstra's algorithm for single-source shortest paths
 * Time: O((V + E) log V) with binary heap
 * Space: O(V) for distances and priority queue
 *
 * @param {Array<Array<Array<number>>>} graph - Adjacency list: graph[from] = [[to, weight], ...]
 * @param {number} source - Starting node
 * @param {number} n - Number of nodes
 * @returns {number[]} - Shortest distance from source to each node
 */
function dijkstra(graph, source, n) {
    const distances = new Array(n).fill(Infinity);
    distances[source] = 0;

    // Priority queue stores [node, distance] pairs
    const pq = new MinPriorityQueue();
    pq.enqueue(source, 0);

    while (!pq.isEmpty()) {
        const { element: node, priority: dist } = pq.dequeue();

        // Skip if we've already found a better path to this node
        if (dist > distances[node]) continue;

        // Relax all edges from current node
        for (const [neighbor, weight] of graph[node] || []) {
            const newDist = dist + weight;

            if (newDist < distances[neighbor]) {
                distances[neighbor] = newDist;
                pq.enqueue(neighbor, newDist);
            }
        }
    }

    return distances;
}

"""
Dijkstra's algorithm using Python's heapq
Time: O((V + E) log V)
Space: O(V)
"""
import heapq

def dijkstra(graph, source, n):
    """
    Find shortest paths from source to all nodes.

    Args:
        graph: Adjacency list - graph[from] = [(to, weight), ...]
        source: Starting node
        n: Number of nodes

    Returns:
        List of shortest distances from source to each node
    """
    distances = [float('inf')] * n
    distances[source] = 0

    # Priority queue: (distance, node)
    pq = [(0, source)]

    while pq:
        dist, node = heapq.heappop(pq)

        # Skip if already processed with better distance
        if dist > distances[node]:
            continue

        # Relax all edges from current node
        for neighbor, weight in graph[node]:
            new_dist = dist + weight

            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))

    return distances

/**
 * Dijkstra's algorithm implementation with PriorityQueue
 * Time: O((V + E) log V)
 * Space: O(V)
 */
import java.util.*;

public class DijkstraTemplate {
    static class Node implements Comparable<Node> {
        int node, distance;

        Node(int node, int distance) {
            this.node = node;
            this.distance = distance;
        }

        public int compareTo(Node other) {
            return Integer.compare(this.distance, other.distance);
        }
    }

    public int[] dijkstra(List<int[]>[] graph, int source, int n) {
        int[] distances = new int[n];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[source] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(source, 0));

        while (!pq.isEmpty()) {
            Node current = pq.poll();

            // Skip if already processed with better distance
            if (current.distance > distances[current.node]) continue;

            // Relax all edges from current node
            for (int[] edge : graph[current.node]) {
                int neighbor = edge[0], weight = edge[1];
                int newDist = current.distance + weight;

                if (newDist < distances[neighbor]) {
                    distances[neighbor] = newDist;
                    pq.offer(new Node(neighbor, newDist));
                }
            }
        }

        return distances;
    }
}

/**
 * Dijkstra's algorithm with priority_queue
 * Time: O((V + E) log V)
 * Space: O(V)
 */
#include <vector>
#include <queue>
#include <climits>

using namespace std;

vector<int> dijkstra(vector<vector<pair<int, int>>>& graph, int source, int n) {
    vector<int> distances(n, INT_MAX);
    distances[source] = 0;

    // Min-heap: {distance, node}
    priority_queue<pair<int, int>,
                 vector<pair<int, int>>,
                 greater<pair<int, int>>> pq;
    pq.push({0, source});

    while (!pq.empty()) {
        auto [dist, node] = pq.top();
        pq.pop();

        // Skip if already processed with better distance
        if (dist > distances[node]) continue;

        // Relax all edges from current node
        for (auto& [neighbor, weight] : graph[node]) {
            int newDist = dist + weight;

            if (newDist < distances[neighbor]) {
                distances[neighbor] = newDist;
                pq.push({newDist, neighbor});
            }
        }
    }

    return distances;
}

/**
 * Dijkstra's algorithm implementation
 * Time: O((V + E) log V)
 * Space: O(V)
 */
package main

import (
    "container/heap"
    "math"
)

// Item represents a node in the priority queue
type Item struct {
    node     int
    priority int
    index    int
}

// PriorityQueue implements heap.Interface
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].priority < pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = i
    pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    old[n-1] = nil
    item.index = -1
    *pq = old[0 : n-1]
    return item
}

func dijkstra(graph [][][2]int, source, n int) []int {
    distances := make([]int, n)
    for i := range distances {
        distances[i] = math.MaxInt32
    }
    distances[source] = 0

    pq := make(PriorityQueue, 0)
    heap.Init(&pq)
    heap.Push(&pq, &Item{node: source, priority: 0})

    for pq.Len() > 0 {
        item := heap.Pop(&pq).(*Item)
        node, dist := item.node, item.priority

        // Skip if already processed with better distance
        if dist > distances[node] {
            continue
        }

        // Relax all edges from current node
        for _, edge := range graph[node] {
            neighbor, weight := edge[0], edge[1]
            newDist := dist + weight

            if newDist < distances[neighbor] {
                distances[neighbor] = newDist
                heap.Push(&pq, &Item{node: neighbor, priority: newDist})
            }
        }
    }

    return distances
}

# Dijkstra's algorithm implementation
# Time: O((V + E) log V)
# Space: O(V)

require 'pq'

def dijkstra(graph, source, n)
  distances = Array.new(n, Float::INFINITY)
  distances[source] = 0

  # Priority queue using ruby-pq gem
  pq = MinPriorityQueue.new
  pq.push([source, 0], 0)

  until pq.empty?
    node, dist = pq.pop

    # Skip if already processed with better distance
    next if dist > distances[node]

    # Relax all edges from current node
    graph[node].each do |neighbor, weight|
      new_dist = dist + weight

      if new_dist < distances[neighbor]
        distances[neighbor] = new_dist
        pq.push([neighbor, new_dist], new_dist)
      end
    end
  end

  distances
end

Code Breakdown

Key Variables:

distances: Array storing shortest distance from source to each node
priority queue (pq): Always extracts node with minimum distance
graph: Adjacency list representation of edges with weights

Algorithm Flow:

  graph TD
    A[Initialize distances: source=0, others=∞] --> B[Add source to priority queue]
    B --> C{Queue empty?}
    C -->|No| D[Extract minimum distance node]
    D --> E{Stale entry?}
    E -->|Yes| C
    E -->|No| F[Relax all edges from node]
    F --> G{Found better path?}
    G -->|Yes| H[Update distance, add to queue]
    G -->|No| I[Skip neighbor]
    H --> C
    I --> C
    C -->|Yes| J[Return distances array]

Critical Sections:

Initialization: Set source distance to 0, all others to infinity
Priority Queue: Always processes closest unvisited node (greedy)
Relaxation: Update neighbor distances when finding better path
Stale Check: Skip queue entries with outdated distances

Bellman-Ford - Negative Edge Support

Description: Handles graphs with negative edge weights and can detect negative cycles. Slower than Dijkstra but more flexible.

/**
 * Bellman-Ford algorithm for graphs with negative edges
 * Time: O(V × E)
 * Space: O(V) for distances
 *
 * @param {Array<Array<number>>} edges - Edge list: [[from, to, weight], ...]
 * @param {number} n - Number of nodes
 * @param {number} source - Starting node
 * @returns {Object} - { distances: number[], hasNegativeCycle: boolean }
 */
function bellmanFord(edges, n, source) {
    const distances = new Array(n).fill(Infinity);
    distances[source] = 0;

    // Relax all edges |V-1| times
    for (let i = 0; i < n - 1; i++) {
        for (const [u, v, weight] of edges) {
            if (distances[u] !== Infinity &&
                distances[u] + weight < distances[v]) {
                distances[v] = distances[u] + weight;
            }
        }
    }

    // Check for negative cycles
    for (const [u, v, weight] of edges) {
        if (distances[u] !== Infinity &&
            distances[u] + weight < distances[v]) {
            return { distances, hasNegativeCycle: true };
        }
    }

    return { distances, hasNegativeCycle: false };
}

"""
Bellman-Ford algorithm with cycle detection
Time: O(V × E)
Space: O(V)
"""
def bellman_ford(edges, n, source):
    """
    Find shortest paths handling negative edges.

    Args:
        edges: List of [from, to, weight] tuples
        n: Number of nodes
        source: Starting node

    Returns:
        (distances, has_negative_cycle) tuple
    """
    distances = [float('inf')] * n
    distances[source] = 0

    # Relax edges |V-1| times
    for _ in range(n - 1):
        for u, v, weight in edges:
            if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight

    # Check for negative cycles
    has_negative_cycle = False
    for u, v, weight in edges:
        if distances[u] != float('inf') and distances[u] + weight < distances[v]:
            has_negative_cycle = True
            break

    return distances, has_negative_cycle

/**
 * Bellman-Ford implementation
 * Time: O(V × E)
 * Space: O(V)
 */
import java.util.*;

public class BellmanFordTemplate {
    static class Result {
        int[] distances;
        boolean hasNegativeCycle;

        Result(int[] distances, boolean hasNegativeCycle) {
            this.distances = distances;
            this.hasNegativeCycle = hasNegativeCycle;
        }
    }

    public Result bellmanFord(List<int[]> edges, int n, int source) {
        int[] distances = new int[n];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[source] = 0;

        // Relax edges |V-1| times
        for (int i = 0; i < n - 1; i++) {
            for (int[] edge : edges) {
                int u = edge[0], v = edge[1], weight = edge[2];
                if (distances[u] != Integer.MAX_VALUE &&
                    distances[u] + weight < distances[v]) {
                    distances[v] = distances[u] + weight;
                }
            }
        }

        // Check for negative cycles
        boolean hasNegativeCycle = false;
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], weight = edge[2];
            if (distances[u] != Integer.MAX_VALUE &&
                distances[u] + weight < distances[v]) {
                hasNegativeCycle = true;
                break;
            }
        }

        return new Result(distances, hasNegativeCycle);
    }
}

/**
 * Bellman-Ford implementation
 * Time: O(V × E)
 * Space: O(V)
 */
#include <vector>
#include <tuple>

using namespace std;

pair<vector<int>, bool> bellman_ford(vector<tuple<int, int, int>>& edges, int n, int source) {
    vector<int> distances(n, INT_MAX);
    distances[source] = 0;

    // Relax edges |V-1| times
    for (int i = 0; i < n - 1; i++) {
        for (auto& [u, v, weight] : edges) {
            if (distances[u] != INT_MAX && distances[u] + weight < distances[v]) {
                distances[v] = distances[u] + weight;
            }
        }
    }

    // Check for negative cycles
    bool has_negative_cycle = false;
    for (auto& [u, v, weight] : edges) {
        if (distances[u] != INT_MAX && distances[u] + weight < distances[v]) {
            has_negative_cycle = true;
            break;
        }
    }

    return {distances, has_negative_cycle};
}

/**
 * Bellman-Ford implementation
 * Time: O(V × E)
 * Space: O(V)
 */
package main

import "math"

type BellmanFordResult struct {
    Distances        []int
    HasNegativeCycle bool
}

func bellmanFord(edges [][3]int, n, source int) BellmanFordResult {
    distances := make([]int, n)
    for i := range distances {
        distances[i] = math.MaxInt32
    }
    distances[source] = 0

    // Relax edges |V-1| times
    for i := 0; i < n-1; i++ {
        for _, edge := range edges {
            u, v, weight := edge[0], edge[1], edge[2]
            if distances[u] != math.MaxInt32 && distances[u]+weight < distances[v] {
                distances[v] = distances[u] + weight
            }
        }
    }

    // Check for negative cycles
    hasNegativeCycle := false
    for _, edge := range edges {
        u, v, weight := edge[0], edge[1], edge[2]
        if distances[u] != math.MaxInt32 && distances[u]+weight < distances[v] {
            hasNegativeCycle = true
            break
        }
    }

    return BellmanFordResult{distances, hasNegativeCycle}
}

# Bellman-Ford algorithm implementation
# Time: O(V × E)
# Space: O(V)

def bellman_ford(edges, n, source)
  distances = Array.new(n, Float::INFINITY)
  distances[source] = 0

  # Relax edges |V-1| times
  (n - 1).times do
    edges.each do |u, v, weight|
      if distances[u] != Float::INFINITY && distances[u] + weight < distances[v]
        distances[v] = distances[u] + weight
      end
    end
  end

  # Check for negative cycles
  has_negative_cycle = false
  edges.each do |u, v, weight|
    if distances[u] != Float::INFINITY && distances[u] + weight < distances[v]
      has_negative_cycle = true
      break
    end
  end

  [distances, has_negative_cycle]
end

BFS - Unweighted Shortest Path

Description: Finds shortest paths in unweighted graphs by exploring nodes level-by-level. Most efficient for grid-based problems and unit-weight graphs.

/**
 * BFS for unweighted shortest paths
 * Time: O(V + E)
 * Space: O(V) for queue and visited
 *
 * @param {Array<Array<number>>} graph - Adjacency list: graph[from] = [to, ...]
 * @param {number} source - Starting node
 * @param {number} target - Target node
 * @param {number} n - Number of nodes
 * @returns {number} - Shortest distance, or -1 if unreachable
 */
function bfsShortestPath(graph, source, target, n) {
    const distances = new Array(n).fill(-1);
    const queue = [source];
    distances[source] = 0;

    while (queue.length > 0) {
        const node = queue.shift();

        if (node === target) return distances[node];

        for (const neighbor of graph[node] || []) {
            if (distances[neighbor] === -1) {
                distances[neighbor] = distances[node] + 1;
                queue.push(neighbor);
            }
        }
    }

    return -1; // No path found
}

"""
BFS using collections.deque for optimal performance
Time: O(V + E)
Space: O(V)
"""
from collections import deque

def bfs_shortest_path(graph, source, target, n):
    """
    Find shortest path in unweighted graph using BFS.

    Args:
        graph: Adjacency list
        source: Starting node
        target: Target node
        n: Number of nodes

    Returns:
        Shortest distance, or -1 if unreachable
    """
    distances = [-1] * n
    queue = deque([source])
    distances[source] = 0

    while queue:
        node = queue.popleft()

        if node == target:
            return distances[node]

        for neighbor in graph[node]:
            if distances[neighbor] == -1:
                distances[neighbor] = distances[node] + 1
                queue.append(neighbor)

    return -1  # No path found

/**
 * Java BFS implementation for unweighted graphs
 * Time: O(V + E)
 * Space: O(V)
 */
import java.util.*;

public class BFSTemplate {
    public int shortestPath(List<Integer>[] graph, int source, int target, int n) {
        int[] distances = new int[n];
        Arrays.fill(distances, -1);

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(source);
        distances[source] = 0;

        while (!queue.isEmpty()) {
            int node = queue.poll();

            if (node == target) return distances[node];

            for (int neighbor : graph[node]) {
                if (distances[neighbor] == -1) {
                    distances[neighbor] = distances[node] + 1;
                    queue.offer(neighbor);
                }
            }
        }

        return -1; // No path found
    }
}

/**
 * C++ BFS implementation
 * Time: O(V + E)
 * Space: O(V)
 */
#include <vector>
#include <queue>

using namespace std;

int bfs_shortest_path(vector<vector<int>>& graph, int source, int target, int n) {
    vector<int> distances(n, -1);
    queue<int> q;
    q.push(source);
    distances[source] = 0;

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        if (node == target) return distances[node];

        for (int neighbor : graph[node]) {
            if (distances[neighbor] == -1) {
                distances[neighbor] = distances[node] + 1;
                q.push(neighbor);
            }
        }
    }

    return -1; // No path found
}

/**
 * Go BFS implementation
 * Time: O(V + E)
 * Space: O(V)
 */
package main

func bfsShortestPath(graph [][]int, source, target, n int) int {
    distances := make([]int, n)
    for i := range distances {
        distances[i] = -1
    }

    queue := []int{source}
    distances[source] = 0

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]

        if node == target {
            return distances[node]
        }

        for _, neighbor := range graph[node] {
            if distances[neighbor] == -1 {
                distances[neighbor] = distances[node] + 1
                queue = append(queue, neighbor)
            }
        }
    }

    return -1 // No path found
}

# BFS implementation for unweighted graphs
# Time: O(V + E)
# Space: O(V)

def bfs_shortest_path(graph, source, target, n)
  distances = Array.new(n, -1)
  queue = [source]
  distances[source] = 0

  until queue.empty?
    node = queue.shift

    return distances[node] if node == target

    graph[node].each do |neighbor|
      if distances[neighbor] == -1
        distances[neighbor] = distances[node] + 1
        queue.push(neighbor)
      end
    end
  end

  -1 # No path found
end

Code Breakdown

Key Variables:

distances: Array tracking shortest distance from source, initialized to -1 (unvisited)
queue: Standard FIFO queue for level-order traversal
graph: Adjacency list of unweighted edges

Algorithm Flow:

  graph TD
    A[Initialize: source=0, others=-1] --> B[Enqueue source]
    B --> C{Queue empty?}
    C -->|No| D[Dequeue next node]
    D --> E{Is this the target?}
    E -->|Yes| F[Return current distance]
    E -->|No| G[For each unvisited neighbor]
    G --> H[Set distance = current + 1]
    H --> I[Enqueue neighbor]
    I --> C
    C -->|Yes| J[Return -1: unreachable]

Critical Sections:

Initialization: Mark source distance as 0, all others as -1 (unvisited)
Level Processing: Each queue iteration represents one “level” or distance increment
Early Exit: Return immediately when target is found (optimal)
Visited Check: Only enqueue unvisited neighbors to prevent cycles

Floyd-Warshall - All Pairs Shortest Path

Description: Computes shortest paths between all pairs of nodes in O(V³) time. Use for dense graphs or when you need all-pairs distances.

/**
 * Floyd-Warshall algorithm for all-pairs shortest paths
 * Time: O(V³)
 * Space: O(V²) for distance matrix
 *
 * @param {Array<Array<Array<number>>>} graph - Adjacency list: graph[from] = [[to, weight], ...]
 * @param {number} n - Number of nodes
 * @returns {Array<Array<number>>} - Distance matrix: dist[i][j] = shortest path from i to j
 */
function floydWarshall(graph, n) {
    const INF = Infinity;

    // Initialize distance matrix
    const dist = Array.from({length: n}, () => new Array(n).fill(INF));

    // Set direct edges and self-loops
    for (let i = 0; i < n; i++) {
        dist[i][i] = 0;
        for (const [j, weight] of graph[i] || []) {
            dist[i][j] = weight;
        }
    }

    // Floyd-Warshall algorithm
    for (let k = 0; k < n; k++) {
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (dist[i][k] !== INF && dist[k][j] !== INF) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    return dist;
}

"""
Floyd-Warshall algorithm with distance matrix
Time: O(V³)
Space: O(V²)
"""
def floyd_warshall(graph, n):
    """
    Compute all-pairs shortest paths.

    Args:
        graph: Adjacency list
        n: Number of nodes

    Returns:
        2D distance matrix
    """
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]

    # Set direct edges and self-loops
    for i in range(n):
        dist[i][i] = 0
        for j, weight in graph[i]:
            dist[i][j] = weight

    # Floyd-Warshall algorithm
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != INF and dist[k][j] != INF:
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist

/**
 * Java Floyd-Warshall implementation
 * Time: O(V³)
 * Space: O(V²)
 */
import java.util.*;

public class FloydWarshallTemplate {
    public int[][] floydWarshall(List<int[]>[] graph, int n) {
        final int INF = Integer.MAX_VALUE / 2; // Avoid overflow

        // Initialize distance matrix
        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 : graph[i]) {
                dist[i][edge[0]] = edge[1];
            }
        }

        // Floyd-Warshall algorithm
        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] != INF && dist[k][j] != INF) {
                        dist[i][j] = Math.min(dist[i][j],
                                          dist[i][k] + dist[k][j]);
                    }
                }
            }
        }

        return dist;
    }
}

/**
 * Floyd-Warshall with 2D vector
 * Time: O(V³)
 * Space: O(V²)
 */
#include <vector>
#include <climits>

using namespace std;

vector<vector<int>> floyd_warshall(vector<vector<pair<int, int>>>& graph, int n) {
    const int INF = INT_MAX / 2;
    vector<vector<int>> dist(n, vector<int>(n, INF));

    // Initialize distance matrix
    for (int i = 0; i < n; i++) {
        dist[i][i] = 0;
        for (auto& [j, weight] : graph[i]) {
            dist[i][j] = weight;
        }
    }

    // Floyd-Warshall algorithm
    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] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    return dist;
}

/**
 * Floyd-Warshall implementation
 * Time: O(V³)
 * Space: O(V²)
 */
package main

import "math"

func floydWarshall(graph [][][2]int, n int) [][]int {
    const INF = math.MaxInt32 / 2
    dist := make([][]int, n)

    for i := range dist {
        dist[i] = make([]int, n)
        for j := range dist[i] {
            dist[i][j] = INF
        }
        dist[i][i] = 0
        for _, edge := range graph[i] {
            dist[i][edge[0]] = edge[1]
        }
    }

    // Floyd-Warshall algorithm
    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if dist[i][k] != INF && dist[k][j] != INF {
                    if dist[i][k]+dist[k][j] < dist[i][j] {
                        dist[i][j] = dist[i][k] + dist[k][j]
                    }
                }
            }
        }
    }

    return dist
}

# Floyd-Warshall algorithm implementation
# Time: O(V³)
# Space: O(V²)

def floyd_warshall(graph, n)
  INF = Float::INFINITY
  dist = Array.new(n) { Array.new(n, INF) }

  # Set direct edges and self-loops
  n.times do |i|
    dist[i][i] = 0
    graph[i].each do |j, weight|
      dist[i][j] = weight
    end
  end

  # Floyd-Warshall algorithm
  n.times do |k|
    n.times do |i|
      n.times do |j|
        if dist[i][k] != INF && dist[k][j] != INF
          dist[i][j] = [dist[i][j], dist[i][k] + dist[k][j]].min
        end
      end
    end
  end

  dist
end

Code Breakdown

Key Variables:

dist: 2D matrix where dist[i][j] = shortest path from i to j
INF: Large value representing no direct connection
k, i, j: Nested loop indices for intermediate node (k) and pair (i, j)

Algorithm Flow:

  graph TD
    A[Initialize dist matrix: direct edges, self=0] --> B[For each intermediate node k]
    B --> C[For each pair i, j]
    C --> D{Reach i to k and k to j?}
    D -->|Yes| E[Update dist = min direct, via k]
    D -->|No| C
    E --> C
    C --> G{All intermediate nodes checked?}
    G -->|No| B
    G -->|Yes| H[Return distance matrix]

Critical Sections:

Matrix Initialization: Set diagonal to 0 (self to self), direct edges to weights, others to INF
Triple Nested Loops: Check if going through intermediate node k improves path i to j
Overflow Protection: Use INF/2 to prevent overflow when summing
Final Matrix: Contains shortest path between every pair of nodes

Practice

Ready to apply these templates? Check out our curated practice problems to build your shortest path problem-solving skills.

Pro Tip: Dijkstra is your go-to for 80% of interview problems. BFS covers unweighted cases. Bellman-Ford and Floyd-Warshall are advanced variants for specific scenarios (negative weights or all-pairs queries).