Learn Shortest Path Algorithms – Guide

01

Introduction to Shortest Path

A shortest path between two nodes in a graph is the path with the minimum total edge weight. These algorithms are fundamental in navigation, networking, and optimization problems.

Key Terminology

Source node: Starting vertex. Relaxation: Updating a node's distance if a shorter path is found. Negative cycle: A cycle whose total weight is negative — makes shortest path undefined.

Algorithm	Time Complexity	Negative Weights	All Pairs
Dijkstra's	O((V+E) log V)	❌ No	❌ No
Bellman-Ford	O(V×E)	✅ Yes	❌ No
Floyd-Warshall	O(V³)	✅ Yes	✅ Yes

Practice: Introduction

Which algorithm would you use for a graph with negative edge weights but no negative cycles, finding single-source shortest paths?

Answer: Bellman-Ford

Dijkstra's fails with negative weights. Floyd-Warshall works but is O(V³) — overkill for single-source. Bellman-Ford handles negative weights in O(V×E).

02

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source node to all other nodes in a graph with non-negative edge weights. It uses a min-heap (priority queue) to always process the nearest unvisited node.

Algorithm Steps

1. Initialize all distances to ∞, source to 0. 2. Push source into min-heap. 3. Pop minimum distance node. 4. For each neighbor, if current distance + edge weight < known distance, update and push to heap. 5. Repeat until heap is empty.

Python

import heapq

def dijkstra(graph, src):
    dist = {node: float('inf') for node in graph}
    dist[src] = 0
    heap = [(0, src)]

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

💡

The if d > dist[u]: continue check is critical — it skips stale entries in the heap, keeping the algorithm correct and efficient.

03

Bellman-Ford Algorithm

Bellman-Ford handles graphs with negative edge weights and can detect negative cycles. It relaxes all edges V-1 times, guaranteeing shortest paths in a graph with no negative cycles.

Algorithm Steps

1. Initialize all distances to ∞, source to 0. 2. Repeat V-1 times: for every edge (u,v,w), if dist[u] + w < dist[v], update dist[v]. 3. Run one more pass — if any distance still updates, a negative cycle exists.

Python

def bellman_ford(vertices, edges, src):
    dist = [float('inf')] * vertices
    dist[src] = 0

    for _ in range(vertices - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return None

    return dist

Practice: Bellman-Ford

Why does Bellman-Ford relax edges exactly V-1 times?

Answer: A shortest path in a graph with V vertices can have at most V-1 edges.

Each relaxation pass guarantees shortest paths using at most k edges. After V-1 passes, all shortest paths are found (assuming no negative cycles).

04

Floyd-Warshall Algorithm

Floyd-Warshall computes all-pairs shortest paths — the shortest path between every pair of vertices. It works with negative weights but not negative cycles.

Core Idea

For each intermediate vertex k, check if routing through k gives a shorter path between every pair (i, j): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Python

def floyd_warshall(matrix):
    n = len(matrix)
    dist = [row[:] for row in matrix]

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

💡

Initialize the distance matrix with 0 on diagonal, actual edge weights where edges exist, and ∞ elsewhere. After running, dist[i][i] < 0 indicates a negative cycle.

05

Practice Exercises

Test your understanding of shortest path algorithms.

Exercise 1: Algorithm Selection

A graph has 1000 vertices, 5000 edges, all non-negative weights. Which algorithm is most efficient for single-source shortest paths?

Answer: Dijkstra's with a min-heap — O((V+E) log V)

No negative weights rules out the need for Bellman-Ford. Floyd-Warshall would be O(10⁹) — too slow. Dijkstra's gives O(6000 × log 1000) ≈ 60,000 operations.

Exercise 2: Negative Cycle Detection

After running Bellman-Ford V-1 times, you do one more relaxation pass and find that dist[3] updates. What does this mean?

Answer: A negative cycle exists reachable from the source.

After V-1 passes all true shortest paths are settled. Any further update means there's a cycle with negative total weight — paths through it keep getting shorter infinitely.

Exercise 3: Floyd-Warshall

For a graph with 4 vertices and edges: A→B=3, B→C=1, A→C=10. After Floyd-Warshall, what is the shortest distance from A to C?

Answer: 4

Direct path A→C = 10. Via B: A→B→C = 3+1 = 4. Floyd-Warshall finds the shorter route through intermediate vertex B.

Algo Infinity Verse

Master Shortest Path Algorithms Dijkstra's, Bellman-Ford & Floyd-Warshall