šŸ’» All-Pairs Shortest Paths with Floyd-Warshall

Compute shortest paths between all node pairs using dynamic programming ā€” input adjacency matrix and watch the global shortest path matrix evolve!

šŸŒ The Network Analyst's Matrix

šŸŽÆ The Challenge:

Sarah has been tasked with developing a program to determine the shortest paths among nodes in a directed network represented as a graph containing nodes and weighted edges.

šŸ“‹ Problem:

Implement the Floyd-Warshall algorithm to compute the shortest path matrix for this directed network.

Problem Specifications

  • Input: n (1 ā‰¤ n ā‰¤ 100). Next n lines: n x n adj matrix (0=diag, 0-999 weights).
  • Output: n x n shortest path matrix, rows space-separated.

Example: Input 1

4
0 3 999 4
8 0 2 999
5 999 0 1
2 999 999 0
0 3 5 4 
5 0 2 3 
3 6 0 1 
2 5 7 0

šŸ”„ Floyd-Warshall Strategy

Key Idea

  1. Init dist = graph (999 as inf).
  2. For k=0 to n-1: for i=0 to n-1: for j=0 to n-1: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
  3. After all k, dist[i][j] = shortest path i to j (or 999 if none).

Note: Considers k as intermediate node. O(n^3) time. Handles negative? No, assumes non-neg.

Floyd-Warshall

Time: O(n^3)
Space: O(n^2)

n Dijkstras

O(n (V+E) log V) ā€” comparable for dense

šŸ” Step-by-Step Floyd-Warshall Demo

Ready. Use controls below to start demo.

Shortest Path Matrix (after k intermediates)

Current k: 0

Final matrix will appear here

Progress Tracker

1. Init dist = graph (999=inf)
2. For each k=0 to n-1 (intermediate)
3. For each i=0 to n-1
4. For each j=0 to n-1: min(dist[i][j], dist[i][k]+dist[k][j])
5. Update if shorter via k
6. Output final dist matrix

šŸŽ® Build Your All-Pairs Shortest Paths

Enter n, matrix and press Compute

Examples

Sample 1 (n=4)
ā†’ Updated matrix with paths via intermediates
Sample 3 (some inf remain)
ā†’ Partial connectivity

šŸ“Š Analysis & Optimization

Time

O(n^3)

Triple loop over n.

Space

O(n^2)

Dist matrix.

Optimization Ideas

  • For sparse graphs, n Dijkstras better: O(n (V+E) log V).
  • Since nā‰¤100, O(n^3)=1e6 fine.
  • In C++, use vector>; const int INF=999;
  • Detect negative cycles? Add check if dist[i][i]<0.