CoursesDSA MasterclassGraphs & Hashing
Advanced·1 min read

Shortest Path Algorithms

Floyd-Warshall algorithm and Warshall's transitive closure.

Shortest Path Algorithms

Floyd-Warshall Algorithm

Finds all-pairs shortest paths in a weighted graph. Works with negative edges (not negative cycles).

Idea: For each intermediate node k, check if going through k gives a shorter path.

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Time: O(V³) | Space: O(V²)

Warshall's Algorithm

Finds the transitive closure - which nodes are reachable from which.

reach[i][j] = reach[i][j] OR (reach[i][k] AND reach[k][j])

When to Use What?

Header
AlgorithmUse CaseTime
Header
BFSUnweighted, single sourceO(V + E)
DijkstraWeighted (non-negative), single sourceO((V+E) log V)
Bellman-FordWeighted (with negative), single sourceO(VE)
Floyd-WarshallAll-pairs shortest pathsO(V³)

Dijkstra's Algorithm

Use a priority queue (min-heap) to always process the closest unvisited vertex.

  • Initialize dist[source] = 0, all others = ∞
  • Push (0, source) to min-heap
  • Pop minimum, relax all edges from that vertex
  • Push updated distances to heap
  • Repeat until heap is empty
Time: O((V + E) log V) with binary heap

Code Example

python
import sys
import heapq

def floyd_warshall(graph):
    V = len(graph)
    dist = [row[:] for row in graph]

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

INF = sys.maxsize
graph = [
    [0,   5,  INF, 10],
    [INF, 0,   3, INF],
    [INF, INF, 0,   1],
    [INF, INF, INF,  0]
]
result = floyd_warshall(graph)
for row in result:
    print([x if x != INF else "INF" for x in row])

def dijkstra(adj, src, V):
    dist = [INF] * V
    dist[src] = 0
    pq = [(0, src)]

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

V = 5
adj = [[] for _ in range(V)]
edges = [(0,1,2),(0,3,6),(1,2,3),(1,3,8),(1,4,5),(2,4,7),(3,4,9)]
for u, v, w in edges:
    adj[u].append((v, w))
    adj[v].append((u, w))
print("Dijkstra distances:", dijkstra(adj, 0, V))

Practice Problems

  • 01Implement Floyd-Warshall and detect negative cycles
  • 02Find the cheapest flights with at most k stops
  • 03Find the shortest path in a grid with obstacles
Graph Fundamentals & BFS/DFSHashing