AlgoMaster

Engineering Solutions

Floyd-Warshall Algorithm (All-Pairs Shortest Path)

Find shortest paths between all pairs of vertices using dynamic programming

Floyd-Warshall Algorithm

Floyd-Warshall finds the shortest paths between all pairs of vertices in a weighted graph, handling both positive and negative edge weights (but no negative cycles).

Theory & Concepts

Definition:

A dynamic programming algorithm that computes shortest paths between all pairs of vertices by considering each vertex as an intermediate point.

Key Points:

  • Works with both positive and negative edge weights
  • Detects negative cycles in the graph
  • Time complexity O(V³) where V is number of vertices
  • Space complexity O(V²) for distance matrix
  • Uses dynamic programming approach with intermediate vertices

Applications:

  • Network routing and traffic engineering
  • Game AI pathfinding in grid-based games
  • Social network analysis for connectivity
  • Transportation and logistics optimization

University Guidelines

Exam Weightage
10-12 marks Marks

Syllabus Coverage:

  • Floyd-Warshall algorithm implementation
  • All-pairs shortest path problem
  • Dynamic programming approach
  • Negative cycle detection
  • Time and space complexity analysis

Common Questions:

  • Implement Floyd-Warshall algorithm
  • Find shortest paths between all vertex pairs
  • Show step-by-step matrix updates
  • Detect negative cycles in graph

Exam Tips:

Draw the initial distance matrix clearly
Show intermediate matrices for each k iteration
Label vertices properly (0 to n-1 or A to N)
Mark when distances get updated in each step

Algorithm Details

O(V³) where V is the number of vertices
Time Complexity
O(V²) for the distance matrix
Space Complexity

Algorithm Steps:

  1. 1Initialize distance matrix D⁰ with edge weights
  2. 2For k = 0 to n-1 (intermediate vertices)
  3. 3 For i = 0 to n-1 (source vertices)
  4. 4 For j = 0 to n-1 (destination vertices)
  5. 5 D^k[i][j] = min(D^(k-1)[i][j], D^(k-1)[i][k] + D^(k-1)[k][j])
  6. 6Final matrix D^n contains all shortest paths

Draw Your Graph

Instructions:

  • Click "Add Node" then click on canvas to add vertices
  • Add Edge: Click "Add Edge", set weight, then click two nodes to connect them
  • Directed edges have arrows showing direction (from first node to second)
  • The first node will turn yellow when selected, then click the second node
  • Click "Delete" then click nodes to remove them (can be undone)
  • Drag nodes to move them around (not available in edge mode)
  • Use Undo/Redo to restore accidentally deleted items
  • Floyd-Warshall works on directed graphs with all-pairs shortest paths

Algorithm Results

🔗

Draw a graph and click "Run Floyd-Warshall Algorithm" to see all-pairs shortest paths