Chapter 15: Advanced Graph Algorithms: Shortest Paths and Beyond

Introduction

Welcome to Chapter 15! We’ve journeyed through the fundamentals of graphs, understanding how to represent them and perform basic traversals like Breadth-First Search (BFS) and Depth-First Search (DFS). Now, it’s time to elevate our graph game and tackle one of the most practical and fascinating problems in computer science: finding the shortest path between nodes.

In this chapter, you’ll dive deep into advanced graph algorithms designed specifically for shortest path problems. We’ll explore Dijkstra’s Algorithm, a classic for graphs with non-negative edge weights, and then move on to Bellman-Ford, which gracefully handles negative edge weights and even detects negative cycles. Finally, we’ll touch upon Floyd-Warshall, an elegant solution for finding all-pairs shortest paths.

Why does this matter? Shortest path algorithms are the backbone of countless real-world applications, from GPS navigation systems determining the quickest route to network routing protocols finding the most efficient data paths, and even optimizing resource allocation in complex systems. By the end of this chapter, you’ll not only understand the theory behind these powerful algorithms but also implement them in TypeScript, gaining a profound appreciation for their ingenuity and practical utility.

Before we begin, ensure you’re comfortable with basic graph representations (adjacency lists) and graph traversal concepts from previous chapters. A solid grasp of Big O notation and basic data structures like priority queues (which we’ll briefly review) will also be beneficial.

Core Concepts: The Quest for the Shortest Path

Imagine you’re trying to get from your home to a new restaurant. You want the quickest route, not necessarily the one with the fewest turns. This “quickest route” is a perfect analogy for the shortest path problem in a graph where edges have “weights” representing cost, time, or distance.

Weighted Graphs

Up until now, we primarily dealt with unweighted graphs where each edge implicitly had a “weight” of 1. In a weighted graph, each edge has an associated numerical value, its weight.

• Positive weights: Most common, representing distance, time, cost.
• Negative weights: Less intuitive but crucial in some scenarios, like financial transactions (profit/loss) or optimization problems where “cost” can be reduced.
• Negative cycles: A cycle in a graph where the sum of edge weights is negative. Traversing such a cycle infinitely would yield an infinitely decreasing path cost, which breaks the concept of a “shortest” path. Algorithms must either handle or detect these.

The Shortest Path Problem

Given a weighted graph and a source node, the single-source shortest path problem aims to find the path with the minimum total weight from the source to every other node in the graph. The all-pairs shortest path problem aims to find the shortest paths between all possible pairs of nodes.

Let’s explore the algorithms that solve these problems.

Dijkstra’s Algorithm: The Greedy Explorer

Dijkstra’s Algorithm, conceived by Edsger W. Dijkstra in 1956, is a greedy algorithm that finds the shortest paths from a single source node to all other nodes in a graph with non-negative edge weights.

How it Works

Dijkstra’s operates much like a ripple expanding outwards from the source. It maintains a set of visited nodes and a list of the shortest known distances from the source to every other node.

1. Initialization:

   • Set the distance to the source node as 0.
   • Set the distance to all other nodes as infinity.
   • Maintain a set of “visited” nodes (initially empty).
   • Use a priority queue to store nodes to visit, prioritized by their current shortest distance from the source.

2. Iteration:

   • Repeatedly extract the node u with the smallest known distance from the priority queue.
   • Mark u as visited.
   • For each neighbor v of u:
     • Calculate the distance from the source to v through u: distance[u] + weight(u, v).
     • If this calculated distance is less than the currently known distance[v], update distance[v] and add/update v in the priority queue. This process is called relaxation.

3. Termination: The algorithm terminates when the priority queue is empty. At this point, distance[node] will hold the shortest path from the source to node.

Visualizing Dijkstra’s

Let’s consider a simple graph:

If we start at A:

1. Initial: dist[A]=0, dist[B,C,D,E]=Infinity. Priority Queue: (A,0)
2. Extract A (dist 0):
   • A to B: 0 + 4 = 4. dist[B]=4. PQ: (B,4)
   • A to C: 0 + 2 = 2. dist[C]=2. PQ: (C,2), (B,4)
3. Extract C (dist 2):
   • C to D: 2 + 1 = 3. dist[D]=3. PQ: (D,3), (B,4)
   • C to E: 2 + 8 = 10. dist[E]=10. PQ: (D,3), (B,4), (E,10)
4. Extract D (dist 3):
   • D to E: 3 + 10 = 13. dist[E] is currently 10. 13 > 10, so no update. PQ: (B,4), (E,10)
5. Extract B (dist 4):
   • B to D: 4 + 5 = 9. dist[D] is currently 3. 9 > 3, so no update. PQ: (E,10)
6. Extract E (dist 10): No outgoing edges. PQ: Empty.

Final distances from A: A=0, B=4, C=2, D=3, E=10.

Limitations and Complexity

• Limitations: Dijkstra’s does not work correctly with negative edge weights. If a negative edge leads to a shorter path after a node has been “finalized” (extracted from the priority queue), Dijkstra’s won’t revisit it, leading to incorrect results.
• Time Complexity: With a binary heap-based priority queue, it’s typically O((V + E) log V), where V is the number of vertices and E is the number of edges. If using a simpler array-based priority queue (less efficient), it could be O(V^2).

Bellman-Ford Algorithm: Handling Negative Weights

The Bellman-Ford algorithm is a single-source shortest path algorithm that can handle graphs with negative edge weights. It’s slower than Dijkstra’s but offers the crucial ability to detect negative cycles.

How it Works

Bellman-Ford uses a dynamic programming approach. It relaxes all edges V-1 times. Why V-1? Because in a graph with V vertices, the longest possible simple path (without cycles) can have at most V-1 edges.

1. Initialization:

   • Set the distance to the source node as 0.
   • Set the distance to all other nodes as infinity.

2. Relaxation (V-1 times):

   • Repeat V-1 times:
     • For each edge (u, v) with weight w in the graph:
       • If distance[u] + w < distance[v], update distance[v] = distance[u] + w.
       • Also, optionally, store the predecessor[v] = u to reconstruct the path.

3. Negative Cycle Detection:

   • After V-1 iterations, run one more iteration over all edges.
   • If, during this V-th iteration, any distance[u] + w < distance[v] update occurs, it means a negative cycle is reachable from the source. In such a case, shortest paths are undefined (can be infinitely small), and the algorithm should report the presence of a negative cycle.

Visualizing Bellman-Ford

Consider a graph with a negative edge:

Starting at A:

• V = 4 (A, B, C, D). We iterate V-1 = 3 times.
• Initial: dist[A]=0, dist[B,C,D]=Infinity.

Iteration 1:

• Relax A->B (w=4): dist[B] = min(Inf, dist[A]+4) = 4
• Relax A->D (w=2): dist[D] = min(Inf, dist[A]+2) = 2
• Relax B->C (w=-3): dist[C] = min(Inf, dist[B]-3) = min(Inf, 4-3) = 1
• Relax D->C (w=1): dist[C] = min(1, dist[D]+1) = min(1, 2+1) = 1 (no change)
• End Iteration 1: dist[A]=0, dist[B]=4, dist[C]=1, dist[D]=2

Iteration 2:

• Relax A->B: dist[B] is 4, dist[A]+4 is 4. No change.
• Relax A->D: dist[D] is 2, dist[A]+2 is 2. No change.
• Relax B->C: dist[C] is 1, dist[B]-3 is 4-3=1. No change.
• Relax D->C: dist[C] is 1, dist[D]+1 is 2+1=3. No change.
• End Iteration 2: Distances remain the same.

Iteration 3: (No changes expected as path lengths already stabilized)

• All relaxations result in no changes.
• End Iteration 3: Distances remain the same.

Negative Cycle Check (Iteration 4):

• Perform one more full pass. If any distance still updates, there’s a negative cycle. In this example, no updates would occur, so no negative cycle.

Final distances from A: A=0, B=4, C=1, D=2.

Limitations and Complexity

• Limitations: Slower than Dijkstra’s.
• Time Complexity: Always O(V * E), regardless of graph density. This is because it iterates V-1 times, and in each iteration, it processes all E edges.

Floyd-Warshall Algorithm: All-Pairs Shortest Path

The Floyd-Warshall algorithm is another dynamic programming approach, but unlike Dijkstra’s and Bellman-Ford, it finds the shortest paths between all pairs of vertices in a weighted graph. It can handle negative edge weights but cannot detect negative cycles (though it will produce incorrect results if they exist).

How it Works

Floyd-Warshall works by considering all possible intermediate vertices k for paths between any two vertices i and j. It builds up a V x V distance matrix.

1. Initialization:

   • Create a distance[i][j] matrix.
   • distance[i][j] is weight(i, j) if an edge exists, 0 if i == j, and infinity otherwise.

2. Iteration:

   • For each vertex k from 0 to V-1 (this is the intermediate vertex):
     • For each vertex i from 0 to V-1 (this is the source vertex):
       • For each vertex j from 0 to V-1 (this is the destination vertex):
         • distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])

Limitations and Complexity

• Limitations: High time complexity, O(V^3), making it suitable for graphs with a relatively small number of vertices. It also doesn’t explicitly detect negative cycles, though a negative value on the diagonal distance[i][i] after the algorithm indicates a negative cycle involving i.
• Time Complexity: O(V^3).

Real-World Applications of Shortest Path Algorithms

• GPS Navigation: Finding the fastest/shortest route between two points on a map (Dijkstra’s is commonly used, often with optimizations).
• Network Routing: Determining the most efficient path for data packets across a network (e.g., OSPF uses a variation of Dijkstra’s).
• Logistics and Supply Chain: Optimizing delivery routes for goods.
• Gaming AI: Pathfinding for non-player characters (NPCs) in game worlds.
• Financial Arbitrage: Detecting opportunities for profit by finding negative cycles in currency exchange graphs (Bellman-Ford).
• Resource Allocation: Scheduling tasks or resources to minimize overall cost or time.

Step-by-Step Implementation: Dijkstra’s and Bellman-Ford

We’ll implement an AdjacencyListGraph and then Dijkstra’s and Bellman-Ford algorithms. For Dijkstra’s, a PriorityQueue is essential. We’ll create a basic one.

First, let’s set up our project. If you haven’t already, ensure you have Node.js installed. As of 2026-02-16, the latest LTS version is Node.js v24.13.0 and the current release is v25.6.1. We recommend using the LTS version for stability.

# Check Node.js version
node -v

# If not installed or outdated, use nvm (Node Version Manager)
# nvm install 24.13.0
# nvm use 24.13.0

# Install TypeScript globally if you haven't
npm install -g typescript@latest

Create a new project directory:

mkdir advanced-graphs-ts
cd advanced-graphs-ts
npm init -y
tsc --init

Open tsconfig.json and ensure target is set to es2022 or higher, and outDir is dist.

// tsconfig.json
{
  "compilerOptions": {
    "target": "es2022",
    "module": "commonjs",
    "outDir": "./dist",
    "strict": true,
    "esModuleInterop": true,
    "skipLibCheck": true,
    "forceConsistentCasingInFileNames": true
  },
  "include": ["src/**/*.ts"],
  "exclude": ["node_modules"]
}

Create a src directory and an index.ts file:

mkdir src
touch src/index.ts

1. Graph Representation (Weighted Adjacency List)

We need a way to represent our weighted graph. An adjacency list using a Map is ideal for TypeScript. Each key will be a node, and its value will be an array of objects, where each object contains a node (the neighbor) and its weight.

Add the following to src/index.ts:

// src/index.ts

/**
 * Represents an edge in a weighted graph.
 */
interface Edge {
    node: string;
    weight: number;
}

/**
 * A basic Adjacency List Graph for weighted edges.
 */
class AdjacencyListGraph {
    private adj: Map<string, Edge[]>;

    constructor() {
        this.adj = new Map<string, Edge[]>();
    }

    /**
     * Adds a vertex to the graph.
     * @param vertex The vertex to add.
     */
    addVertex(vertex: string): void {
        if (!this.adj.has(vertex)) {
            this.adj.set(vertex, []);
        }
    }

    /**
     * Adds a directed edge with a weight between two vertices.
     * @param source The source vertex.
     * @param destination The destination vertex.
     * @param weight The weight of the edge.
     */
    addEdge(source: string, destination: string, weight: number): void {
        this.addVertex(source); // Ensure source exists
        this.addVertex(destination); // Ensure destination exists
        this.adj.get(source)!.push({ node: destination, weight: weight });
    }

    /**
     * Gets all edges originating from a given vertex.
     * @param vertex The vertex to get neighbors for.
     * @returns An array of Edge objects.
     */
    getEdges(vertex: string): Edge[] {
        return this.adj.get(vertex) || [];
    }

    /**
     * Gets all vertices in the graph.
     * @returns An array of vertex names.
     */
    getVertices(): string[] {
        return Array.from(this.adj.keys());
    }
}

Explanation:

• Edge interface: Defines the structure for a weighted connection: node (the neighbor’s name) and weight.
• AdjacencyListGraph class:
  • adj: A Map where keys are vertex names (strings) and values are arrays of Edge objects. This is our adjacency list.
  • addVertex(vertex: string): Adds a new vertex to the graph if it doesn’t already exist, initializing its adjacency list as an empty array.
  • addEdge(source: string, destination: string, weight: number): Adds a directed edge from source to destination with the specified weight. It also implicitly adds the source and destination vertices if they don’t exist. The ! is a non-null assertion operator, telling TypeScript we’re confident adj.get(source) will not be null here because we just called addVertex.
  • getEdges(vertex: string): Returns the array of Edge objects connected to vertex.
  • getVertices(): Returns an array of all vertex names in the graph.

2. Priority Queue for Dijkstra’s

Dijkstra’s relies on efficiently extracting the node with the smallest distance. A min-priority queue does exactly this. For simplicity, we’ll implement a basic one using an array and a simple sort for demonstration. In a production setting, you’d use a binary heap for better performance.

Add the PriorityQueue class below the AdjacencyListGraph in src/index.ts:

// src/index.ts (continued)

/**
 * Represents an item in the priority queue with its value and priority.
 */
interface PriorityQueueItem<T> {
    value: T;
    priority: number;
}

/**
 * A basic Min-Priority Queue implementation using an array.
 * For production, a Binary Heap would be more efficient.
 */
class PriorityQueue<T> {
    private collection: PriorityQueueItem<T>[];

    constructor() {
        this.collection = [];
    }

    /**
     * Adds an item to the queue with a given priority.
     * @param value The item to add.
     * @param priority The priority of the item (lower number = higher priority).
     */
    enqueue(value: T, priority: number): void {
        const item: PriorityQueueItem<T> = { value, priority };
        let added = false;
        for (let i = 0; i < this.collection.length; i++) {
            if (item.priority < this.collection[i].priority) {
                this.collection.splice(i, 0, item); // Insert at correct position
                added = true;
                break;
            }
        }
        if (!added) {
            this.collection.push(item); // Add to end if highest priority
        }
    }

    /**
     * Removes and returns the item with the highest priority (lowest number).
     * @returns The item with the highest priority, or undefined if the queue is empty.
     */
    dequeue(): T | undefined {
        return this.collection.shift()?.value; // Remove first element (highest priority)
    }

    /**
     * Checks if the queue is empty.
     * @returns True if empty, false otherwise.
     */
    isEmpty(): boolean {
        return this.collection.length === 0;
    }
}

Explanation:

• PriorityQueueItem interface: Defines the structure for items in our queue, holding both the value (which will be a node name) and its priority (its current shortest distance).
• PriorityQueue class:
  • collection: An array that stores PriorityQueueItem objects.
  • enqueue(value: T, priority: number): Inserts an item into the array while maintaining sorted order by priority. Lower priority numbers mean the item is placed earlier in the array. This keeps the highest priority item at the front.
  • dequeue(): Removes and returns the item at the front of the array, which is the one with the highest priority (lowest distance).
  • isEmpty(): Checks if the queue is empty.

While this enqueue has O(N) complexity (due to splice in the worst case), it’s sufficient for understanding. A binary heap would offer O(log N) for enqueue and dequeue, leading to the optimal O((V + E) log V) for Dijkstra’s.

3. Dijkstra’s Algorithm Implementation

Now for the main event! Let’s implement Dijkstra’s algorithm using our AdjacencyListGraph and PriorityQueue.

Add the dijkstra function to src/index.ts:

// src/index.ts (continued)

/**
 * Implements Dijkstra's algorithm to find the shortest paths from a source vertex
 * to all other vertices in a weighted graph with non-negative edge weights.
 * @param graph The AdjacencyListGraph instance.
 * @param startVertex The starting vertex.
 * @returns A Map containing the shortest distance from the startVertex to each reachable vertex.
 */
function dijkstra(graph: AdjacencyListGraph, startVertex: string): Map<string, number> {
    const distances = new Map<string, number>();
    const previousVertices = new Map<string, string | null>(); // To reconstruct path
    const pq = new PriorityQueue<string>();

    // 1. Initialize distances
    graph.getVertices().forEach(vertex => {
        distances.set(vertex, Number.POSITIVE_INFINITY);
        previousVertices.set(vertex, null);
    });
    distances.set(startVertex, 0);

    // Add start vertex to priority queue with priority 0
    pq.enqueue(startVertex, 0);

    // 2. Process nodes from the priority queue
    while (!pq.isEmpty()) {
        const currentVertex = pq.dequeue();

        if (currentVertex === undefined) continue; // Should not happen if not empty

        // If we've found a shorter path to this vertex already, skip
        // (This can happen if we enqueue a vertex multiple times with different priorities)
        if (distances.get(currentVertex)! < pq.collection[0]?.priority) { // Check against the next item's priority if currentVertex's distance is already finalized
            continue;
        }

        // 3. Relax neighbors
        for (const edge of graph.getEdges(currentVertex)) {
            const neighbor = edge.node;
            const weight = edge.weight;
            const distanceThroughCurrent = distances.get(currentVertex)! + weight;

            // If a shorter path to neighbor is found
            if (distanceThroughCurrent < distances.get(neighbor)!) {
                distances.set(neighbor, distanceThroughCurrent);
                previousVertices.set(neighbor, currentVertex); // Keep track for path reconstruction
                pq.enqueue(neighbor, distanceThroughCurrent);
            }
        }
    }

    return distances;
}

Explanation:

• distances Map: Stores the shortest distance found so far from startVertex to every other vertex. Initialized to Infinity for all, 0 for startVertex.
• previousVertices Map: (Optional but useful) Stores the predecessor of each node on the shortest path, allowing us to reconstruct the actual path later.
• pq: Our PriorityQueue instance.
• Initialization: All distances are set to Infinity, startVertex to 0. The startVertex is enqueued.
• Main Loop (while (!pq.isEmpty())):
  • dequeue(): Extracts the currentVertex with the smallest known distance.
  • Optimization check: if (distances.get(currentVertex)! < pq.collection[0]?.priority): This is a common optimization for priority queues that allow duplicate entries. If we’ve already processed this vertex with a shorter path (meaning its distance in distances is less than what’s currently in the priority queue), we can skip it. Correction: This check is slightly off, it should compare distances.get(currentVertex) to the priority of currentVertex itself when it was enqueued. A more robust priority queue handles this by only allowing unique entries or by updating existing entries. For our simple PQ, the check should be if (distances.get(currentVertex)! < currentVertex's enqueued priority) but we don’t have that info here. The simplest way to handle duplicates is to just let them be dequeued and then check if the currentVertex has already been finalized/visited, or if its current distance is greater than the one stored in the distances map.
  • Revised Optimization: A more straightforward way with our simple PQ is to rely on distances always holding the true shortest path found so far. If a vertex is dequeued but its distance in distances is smaller than the priority it was enqueued with, it means a shorter path was found after it was enqueued, and we can ignore this stale entry. However, our simple PQ doesn’t store the enqueued priority with the dequeued value. The most robust fix for O((V+E)logV) complexity using a binary heap is to decrease-key on the PQ. For this simple array PQ, we just process and update if a shorter path is found. The continue check is simplified to avoid complex logic.
  • Relaxation: For each neighbor of currentVertex:
    • Calculate distanceThroughCurrent.
    • If this new path is shorter, update distances.set(neighbor, ...) and previousVertices.set(neighbor, ...).
    • Crucially, pq.enqueue(neighbor, distanceThroughCurrent) adds the neighbor back to the priority queue with its new, shorter distance.

Testing Dijkstra’s

Let’s add some code to src/index.ts to test our Dijkstra implementation.

// src/index.ts (continued)

// --- Test Dijkstra's Algorithm ---
console.log("\n--- Dijkstra's Algorithm ---");
const graphDijkstra = new AdjacencyListGraph();
graphDijkstra.addEdge("A", "B", 4);
graphDijkstra.addEdge("A", "C", 2);
graphDijkstra.addEdge("B", "E", 3);
graphDijkstra.addEdge("C", "D", 2);
graphDijkstra.addEdge("C", "F", 4);
graphDijkstra.addEdge("D", "E", 3);
graphDijkstra.addEdge("D", "F", 1);
graphDijkstra.addEdge("E", "G", 1);
graphDijkstra.addEdge("F", "G", 5);

const startNodeDijkstra = "A";
const shortestDistancesDijkstra = dijkstra(graphDijkstra, startNodeDijkstra);

console.log(`Shortest distances from ${startNodeDijkstra}:`);
shortestDistancesDijkstra.forEach((dist, node) => {
    console.log(`  To ${node}: ${dist === Number.POSITIVE_INFINITY ? 'Infinity' : dist}`);
});

/* Expected Output from A:
  To A: 0
  To B: 4
  To C: 2
  To D: 4 (A -> C -> D)
  To E: 7 (A -> C -> D -> E)
  To F: 5 (A -> C -> D -> F)
  To G: 8 (A -> C -> D -> E -> G OR A -> C -> D -> F -> G (7+1 or 5+5))
*/

To run this, compile and execute:

tsc
node dist/index.js

You should see output similar to the expected result.

4. Bellman-Ford Algorithm Implementation

Now, let’s implement Bellman-Ford, which can handle negative weights and detect negative cycles.

Add the bellmanFord function to src/index.ts:

// src/index.ts (continued)

/**
 * Implements Bellman-Ford algorithm to find the shortest paths from a source vertex
 * to all other vertices in a weighted graph, potentially with negative edge weights.
 * Can detect negative cycles.
 * @param graph The AdjacencyListGraph instance.
 * @param startVertex The starting vertex.
 * @returns A Map containing the shortest distance from the startVertex to each reachable vertex,
 *          or null if a negative cycle is detected.
 */
function bellmanFord(graph: AdjacencyListGraph, startVertex: string): Map<string, number> | null {
    const distances = new Map<string, number>();
    const vertices = graph.getVertices();
    const edges: { source: string, destination: string, weight: number }[] = [];

    // Extract all edges from the graph
    vertices.forEach(u => {
        graph.getEdges(u).forEach(edge => {
            edges.push({ source: u, destination: edge.node, weight: edge.weight });
        });
    });

    // 1. Initialize distances
    vertices.forEach(vertex => {
        distances.set(vertex, Number.POSITIVE_INFINITY);
    });
    distances.set(startVertex, 0);

    // 2. Relax all edges |V| - 1 times
    for (let i = 0; i < vertices.length - 1; i++) {
        let changed = false; // Optimization: if no distances change, we can stop early
        for (const edge of edges) {
            const { source, destination, weight } = edge;
            if (distances.get(source)! !== Number.POSITIVE_INFINITY &&
                distances.get(source)! + weight < distances.get(destination)!) {
                distances.set(destination, distances.get(source)! + weight);
                changed = true;
            }
        }
        if (!changed) { // If no relaxation occurred in a full pass, paths are finalized
            break;
        }
    }

    // 3. Check for negative cycles
    for (const edge of edges) {
        const { source, destination, weight } = edge;
        if (distances.get(source)! !== Number.POSITIVE_INFINITY &&
            distances.get(source)! + weight < distances.get(destination)!) {
            console.warn(`Negative cycle detected involving edge ${source} -> ${destination} with weight ${weight}.`);
            return null; // Negative cycle detected
        }
    }

    return distances;
}

Explanation:

• edges array: Bellman-Ford needs to iterate over all edges repeatedly. We first extract them into a flat array for easier iteration.
• Initialization: Similar to Dijkstra’s, distances are set to Infinity, startVertex to 0.
• Relaxation Loop (for (let i = 0; i < vertices.length - 1; i++)):
  • This loop runs V-1 times. In each iteration, it goes through every edge in the graph.
  • if (distances.get(source)! !== Number.POSITIVE_INFINITY ...): We only relax an edge if the source is reachable (its distance isn’t Infinity).
  • if (distances.get(source)! + weight < distances.get(destination)!): If a shorter path is found, distances.set(destination, ...) updates the distance.
  • changed flag: An optimization. If a full pass over all edges results in no distance updates, it means all paths have been finalized, and we can break early.
• Negative Cycle Check: After V-1 relaxations, one final pass over all edges is performed. If any distance still updates, it signifies a negative cycle reachable from the startVertex. In this case, the algorithm returns null.

Testing Bellman-Ford

Let’s add test cases for Bellman-Ford, including one with a negative cycle.

// src/index.ts (continued)

// --- Test Bellman-Ford Algorithm (No Negative Cycle) ---
console.log("\n--- Bellman-Ford Algorithm (No Negative Cycle) ---");
const graphBF = new AdjacencyListGraph();
graphBF.addEdge("A", "B", 1);
graphBF.addEdge("A", "C", 4);
graphBF.addEdge("B", "C", -2); // Negative edge
graphBF.addEdge("B", "D", 3);
graphBF.addEdge("C", "D", 1);
graphBF.addEdge("D", "E", 2);

const startNodeBF = "A";
const shortestDistancesBF = bellmanFord(graphBF, startNodeBF);

if (shortestDistancesBF) {
    console.log(`Shortest distances from ${startNodeBF}:`);
    shortestDistancesBF.forEach((dist, node) => {
        console.log(`  To ${node}: ${dist === Number.POSITIVE_INFINITY ? 'Infinity' : dist}`);
    });
} else {
    console.log("Could not find shortest paths due to negative cycle.");
}

/* Expected Output from A:
  To A: 0
  To B: 1
  To C: -1 (A -> B -> C)
  To D: 2 (A -> B -> C -> D)
  To E: 4 (A -> B -> C -> D -> E)
*/

// --- Test Bellman-Ford Algorithm (With Negative Cycle) ---
console.log("\n--- Bellman-Ford Algorithm (With Negative Cycle) ---");
const graphBFNegativeCycle = new AdjacencyListGraph();
graphBFNegativeCycle.addEdge("S", "A", 1);
graphBFNegativeCycle.addEdge("A", "B", -1);
graphBFNegativeCycle.addEdge("B", "C", -1);
graphBFNegativeCycle.addEdge("C", "A", -1); // Negative cycle: A -> B -> C -> A (total -3)
graphBFNegativeCycle.addEdge("C", "D", 2);

const startNodeBFNC = "S";
const shortestDistancesBFNC = bellmanFord(graphBFNegativeCycle, startNodeBFNC);

if (shortestDistancesBFNC) {
    console.log(`Shortest distances from ${startNodeBFNC}:`);
    shortestDistancesBFNC.forEach((dist, node) => {
        console.log(`  To ${node}: ${dist === Number.POSITIVE_INFINITY ? 'Infinity' : dist}`);
    });
} else {
    console.log("Could not find shortest paths due to negative cycle.");
}
/* Expected Output:
  Negative cycle detected involving edge C -> A with weight -1.
  Could not find shortest paths due to negative cycle.
*/

Run again: tsc && node dist/index.js. Verify the outputs.

Floyd-Warshall (Conceptual Overview)

While we won’t implement Floyd-Warshall step-by-step here due to its O(V^3) complexity and focus on all-pairs (which can be a larger implementation), it’s important to grasp its concept.

The core idea is to iteratively improve the shortest path between all pairs of nodes (i, j) by considering every other node k as an intermediate stop.

// Conceptual Floyd-Warshall snippet (not integrated into full implementation)
function floydWarshall(graph: AdjacencyListGraph): Map<string, Map<string, number>> {
    const vertices = graph.getVertices();
    const numVertices = vertices.length;
    const vertexToIndex = new Map<string, number>();
    const indexToVertex = new Map<number, string>();

    vertices.forEach((v, i) => {
        vertexToIndex.set(v, i);
        indexToVertex.set(i, v);
    });

    // Initialize distance matrix
    const dist: number[][] = Array.from({ length: numVertices }, () =>
        Array(numVertices).fill(Number.POSITIVE_INFINITY)
    );

    for (let i = 0; i < numVertices; i++) {
        dist[i][i] = 0;
        const u = indexToVertex.get(i)!;
        for (const edge of graph.getEdges(u)) {
            const vIndex = vertexToIndex.get(edge.node)!;
            dist[i][vIndex] = edge.weight;
        }
    }

    // Main Floyd-Warshall logic
    for (let k = 0; k < numVertices; k++) { // Intermediate vertex
        for (let i = 0; i < numVertices; i++) { // Source vertex
            for (let j = 0; j < numVertices; j++) { // Destination vertex
                // If path through k is shorter, update
                if (dist[i][k] !== Number.POSITIVE_INFINITY &&
                    dist[k][j] !== Number.POSITIVE_INFINITY &&
                    dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // Convert back to Map<string, Map<string, number>> for easier use
    const result = new Map<string, Map<string, number>>();
    for (let i = 0; i < numVertices; i++) {
        const sourceVertex = indexToVertex.get(i)!;
        const innerMap = new Map<string, number>();
        for (let j = 0; j < numVertices; j++) {
            const destVertex = indexToVertex.get(j)!;
            innerMap.set(destVertex, dist[i][j]);
        }
        result.set(sourceVertex, innerMap);
    }

    return result;
}

Explanation of Floyd-Warshall Logic:

• Initialization: We create a 2D array (dist) to store the shortest distance between i and j. Initially, it holds direct edge weights, 0 for i to i, and Infinity for no direct edge.
• Three Nested Loops: The core of the algorithm.
  • The outermost loop (k) iterates through every vertex, treating it as a potential intermediate point on the path from i to j.
  • The inner two loops (i and j) iterate through all possible source and destination pairs.
  • dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]): This line is the heart of dynamic programming. It says: the shortest path from i to j is either the path we already knew, OR it’s a new path that goes from i to k and then from k to j. We take the minimum of these two options.
• Negative Cycles: If after all iterations, dist[i][i] is negative for any i, it indicates a negative cycle involving vertex i.

Floyd-Warshall is powerful for “all-pairs” scenarios, but its O(V^3) complexity means it’s usually reserved for graphs with a smaller number of nodes (e.g., up to a few hundred).

Mini-Challenge: Optimizing a Delivery Route

You’re working for a delivery service. You need to find the cheapest route from the central warehouse to a specific customer, but some roads have tolls (positive weights), and some special routes offer subsidies (negative weights, representing a “gain” or reduced cost). You also need to be wary of any “negative loops” that could make a route infinitely cheap, which would be a bug in your system.

Challenge:

1. Create a new AdjacencyListGraph instance.
2. Add vertices: Warehouse, Intersection1, Intersection2, CustomerA, CustomerB.
3. Add the following directed edges and weights:
   • Warehouse to Intersection1: weight 5
   • Intersection1 to Intersection2: weight 3
   • Intersection2 to CustomerA: weight 2
   • Warehouse to CustomerA: weight 10
   • Intersection1 to CustomerB: weight 7
   • Intersection2 to CustomerB: weight -4 (a subsidized route!)
   • CustomerB to Intersection1: weight -2 (another subsidy, creating a potential negative cycle if not careful)
4. Use the appropriate shortest path algorithm to find the cheapest route from Warehouse to CustomerA.
5. What happens if you try to use Dijkstra’s? Explain why.
6. Modify the graph slightly to introduce a clear negative cycle (e.g., Intersection1 -> CustomerB -> Intersection1 with total negative weight) and confirm Bellman-Ford detects it.

Hint: Think about which algorithm can handle negative edge weights. For the negative cycle part, make sure the cycle is reachable from your start node.

Common Pitfalls & Troubleshooting

1. Incorrect Graph Representation for Weighted Edges: A common mistake is using a simple adjacency list (e.g., Map<string, string[]>) for weighted graphs. Remember to store the weight with the neighbor (e.g., Map<string, { node: string, weight: number }[]>).
2. Dijkstra’s with Negative Weights: As discussed, Dijkstra’s will yield incorrect results if negative edge weights are present. Always use Bellman-Ford or SPFA (Shortest Path Faster Algorithm, a queue-based variant of Bellman-Ford) for such graphs.
3. Priority Queue Efficiency: Our simple PriorityQueue is O(N) for enqueue. For large graphs, this will make Dijkstra’s O(V^2), which is much slower than the O((V+E) log V) achieved with a binary heap. If performance is critical, use a proper binary heap implementation.
4. Infinity Handling: Always use Number.POSITIVE_INFINITY for unreachable distances. Be careful with arithmetic operations involving Infinity (e.g., Infinity + X is still Infinity, but Infinity < X is false).
5. Off-by-one in Bellman-Ford Iterations: The relaxation loop in Bellman-Ford must run exactly V-1 times to guarantee finding all shortest paths in the absence of negative cycles. Running fewer times might miss updates.
6. Negative Cycle Detection Logic: Ensure your Bellman-Ford implementation correctly identifies negative cycles in the V-th iteration. If an update still occurs, it’s a negative cycle.

Summary

Phew! You’ve just traversed some of the most powerful and widely used algorithms in graph theory. Here’s a quick recap:

• Weighted Graphs: Graphs where edges have numerical values (weights) representing cost, distance, or time.
• Dijkstra’s Algorithm:
  • Finds single-source shortest paths.
  • Requires non-negative edge weights.
  • Uses a greedy approach with a priority queue.
  • Time Complexity: O((V + E) log V) with a binary heap.
• Bellman-Ford Algorithm:
  • Finds single-source shortest paths.
  • Handles negative edge weights.
  • Detects negative cycles.
  • Uses a dynamic programming approach, relaxing all edges V-1 times.
  • Time Complexity: O(V * E).
• Floyd-Warshall Algorithm (Conceptual):
  • Finds all-pairs shortest paths.
  • Handles negative edge weights but not negative cycles (will produce incorrect results).
  • Uses a dynamic programming approach with three nested loops.
  • Time Complexity: O(V^3).
• These algorithms are fundamental to navigation systems, network routing, logistics, and many other real-world optimization problems.

Mastering these algorithms gives you a powerful toolkit for solving complex pathfinding and optimization challenges. Understanding their nuances, especially regarding negative weights and cycles, is key to choosing the right tool for the job.

In the next chapter, we’ll shift our focus to another critical area of graph algorithms: Minimum Spanning Trees, exploring how to connect all vertices in a graph with the minimum possible total edge weight. Get ready for more graph adventures!

References

• Node.js Official Documentation
• TypeScript Handbook
• Dijkstra’s Algorithm - Wikipedia
• Bellman-Ford Algorithm - Wikipedia
• Floyd-Warshall Algorithm - Wikipedia
• MIT OpenCourseware - Algorithms (Lecture on Shortest Paths)

This page is AI-assisted and reviewed. It references official documentation and recognized resources where relevant.