Graph AlgorithmsAdvanced

Floyd-Warshall Algorithm

All-pairs shortest path algorithm that computes distances between every pair of vertices in O(V³) time. Uses dynamic programming with elegant three-line core logic. Handles negative weights and provides transitive closure. Ideal for dense graphs, network analysis, and when all pairwise distances are needed.

#graph#all-pairs-shortest-paths#dynamic-programming#transitive-closure

Complexity Analysis

Time (Average)

O(V³)

Expected case performance

Space

O(V²)

Memory requirements

Time (Best)

O(V³)

Best case performance

Time (Worst)

O(V³)

Worst case performance

📚 CLRS Reference

Introduction to Algorithms•Chapter 25•Section 25.2

Number of Vertices (3-6)

Adjacency Matrix (use ∞ for infinity)

Each row on a new line, comma-separated

Example Graphs:

How it works

• All-pairs shortest paths algorithm
• Uses dynamic programming approach
• O(V³) time, O(V²) space complexity
• Handles negative edge weights
• Formula: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Step: 1 / 0

Animation Speed500ms

SlowFast

Keyboard Shortcuts

Space Play/Pause← → StepR Reset1-4 Speed

Real-time Statistics

Algorithm Performance Metrics

Progress0%

Comparisons

Swaps

Array Accesses

Steps

1/ 0

Algorithm Visualization

Step 1 of 0

Initialize array to begin

Default

Comparing

Swapped

Sorted

Code Execution

Currently executing

Previously executed

Implementation

Related Algorithms

View all in Graph Algorithms

Breadth-First Search (BFS)

Intermediate

Explores a graph level by level, visiting all vertices at the current depth before moving deeper. Uses a queue and is ideal for finding shortest paths in unweighted graphs. Applications include maze solving, social network analysis, and finding connections between nodes.

Depth-First Search (DFS)

Intermediate

Explores a graph by going as deep as possible along each path before backtracking. Implemented using a stack or recursion, making it natural for recursive problems. Used for pathfinding, cycle detection, topological sorting, and maze generation.

Dijkstra's Algorithm

Advanced

Finds the shortest paths from a single source vertex to all other vertices in a weighted graph. Powers GPS navigation systems and network routing protocols. Works efficiently with non-negative edge weights using a greedy approach with a priority queue.

Back to Graph Algorithms