Floyd-Warshall Algorithm

Introduction

i. Floyd-Warshall Algorithm finds shortest paths between all pairs of nodes.

ii. Works on weighted, directed or undirected graphs.

iii. Uses dynamic programming.

iv. No negative weight cycles allowed.

Key Points

Graph Type: Weighted, directed or undirected

Handles negative edge weights (no negative cycles)

Output: Matrix of shortest path distances

Algorithm Steps

i. Initialize distance matrix dist[][]

ii. For each intermediate vertex k = 0 to V-1

   For each source vertex i = 0 to V-1

   For each destination vertex j = 0 to V-1

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

Pseudocode

Example

Input: dist[][] = [[0, 4, 10⁸, 5, 10⁸],
[10⁸, 0, 1, 10⁸, 6],
[2, 10⁸, 0, 3, 10⁸],
[10⁸, 10⁸, 1, 0, 2],
[1, 10⁸, 10⁸, 4, 0]]

Output:[[0, 4, 5, 5, 7],
[3, 0, 1, 4, 6],
[2, 6, 0, 3, 5],
[3, 7, 1, 0, 2],
[1, 5, 5, 4, 0]]

Explanation:

Complexity

Time Complexity: O(V³)

Space Complexity: O(V²)

Best for dense graphs

Use Case

Used in network routing, map applications, transport systems

Calculates shortest distances between every location pair

All-pairs routing in networks

Flight and transportation systems