Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Floyd Warshall Algorithm
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

The Floyd-Warshall algorithm is a fundamental algorithm in computer science used for finding shortest paths in a weighted graph with positive or negative edge weights (but no negative cycles). It is particularly useful for dense graphs where we need to compute shortest paths between all pairs of vertices. The algorithm works by progressively improving the estimate of the shortest path between any two vertices by considering all possible paths through intermediate vertices.

  • Goal: To find the shortest path between all pairs of vertices in a weighted graph.
  • Approach: Dynamic Programming. The algorithm iteratively updates the shortest path estimates by considering paths that pass through intermediate vertices.

The Floyd-Warshall algorithm uses a distance matrix, where the entry at row i and column j represents the shortest distance from vertex i to vertex j. Initially, this matrix is populated with direct edge weights, and the algorithm systematically updates it to reflect the shortest paths considering all possible intermediate vertices.

Step-by-Step Algorithm

  1. Initialize the Distance Matrix:

    • Create a matrix to store the shortest distances between all pairs of vertices.
    • Initialize the matrix with the input graph’s edge weights. Use a large value (INF) to represent the absence of an edge.
  2. Iterate Over All Pairs of Vertices:

    • For each pair of vertices (i, j), update the distance between them considering each vertex as an intermediate vertex.
    • If the path from i to j through vertex k is shorter than the direct path from i to j, update the distance matrix.
  3. Update Distance Matrix:

    • For each pair of vertices (i, j), update the distance as: ( \text{distance}[i][j] = \min(\text{distance}[i][j], \text{distance}[i][k] + \text{distance}[k][j]) )
    • Repeat this process for all vertices as the intermediate vertex.
  4. Print the Final Distance Matrix:

    • After processing all vertices, the distance matrix will contain the shortest distances between all pairs of vertices.

Algorithm Walkthrough

Consider the example graph represented by the following adjacency matrix:

Graph:
{
    { 0, 2, INF, 6 },
    { INF, 0, 3, 8 },
    { INF, INF, 0, 1 },
    { INF, INF, INF, 0 }
}
  1. Initialize the Distance Matrix:

    Distance Matrix:
    {
        { 0, 2, INF, 6 },
        { INF, 0, 3, 8 },
        { INF, INF, 0, 1 },
        { INF, INF, INF, 0 }
    }
    
  2. Iterate Over All Pairs of Vertices:

    • Using Vertex 0 as Intermediate:

      Updated Distance Matrix:
      {
          { 0, 2, INF, 6 },
          { INF, 0, 3, 8 },
          { INF, INF, 0, 1 },
          { INF, INF, INF, 0 }
      }
      (No change since there are no shorter paths through vertex 0)
      
    • Using Vertex 1 as Intermediate:

      Updated Distance Matrix:
      {
          { 0, 2, 5, 6 },
          { INF, 0, 3, 8 },
          { INF, INF, 0, 1 },
          { INF, INF, INF, 0 }
      }
      (Distance from 0 to 2 updated from INF to 5 through vertex 1)
      
    • Using Vertex 2 as Intermediate:

      Updated Distance Matrix:
      {
          { 0, 2, 5, 6 },
          { INF, 0, 3, 4 },
          { INF, INF, 0, 1 },
          { INF, INF, INF, 0 }
      }
      (Distance from 1 to 3 updated from 8 to 4 through vertex 2)
      
    • Using Vertex 3 as Intermediate:

      Final Distance Matrix:
      {
          { 0, 2, 5, 6 },
          { INF, 0, 3, 4 },
          { INF, INF, 0, 1 },
          { INF, INF, INF, 0 }
      }
      (No further changes)
      
  3. Print the Final Distance Matrix:

    • The final distance matrix represents the shortest distances between all pairs of vertices in the graph.

Code

Python3
Python3

. . . .

Complexity Analysis

Time Complexity

The Floyd-Warshall algorithm runs in O(V^3) time, where (V) is the number of vertices in the graph. This is because the algorithm consists of three nested loops, each running (V) times.

Space Complexity

The space complexity is O(V^2) because we need to store the distance matrix, which holds the shortest distances between every pair of vertices.

Differences Between Dijkstra's, Bellman-Ford, and Floyd-Warshall Algorithms

FeatureDijkstra's AlgorithmBellman-Ford AlgorithmFloyd-Warshall Algorithm
PurposeSingle-source shortest path for all nodes in a graphSingle-source shortest path for all nodes in a graphAll-pairs shortest path for all nodes in a graph
Graph TypeWorks only with non-negative weightsHandles both positive and negative weights (no negative cycles)Handles both positive and negative weights (no negative cycles)
Time ComplexityO(V^2) for matrix representation, O(E + V \log V) with a min-heapO(VE)O(V^3)
Space ComplexityO(V^2) for adjacency matrix, O(E + V) for adjacency listO(V) for distance arrayO(V^2)
Dynamic ProgrammingNoYesYes
Greedy ApproachYesNoNo
Negative WeightsNoYes (handles negative weights)Yes (handles negative weights)
Negative CyclesNoDetects negative cyclesDetects negative cycles
Use CaseFinding shortest path from a single source to all nodesFinding shortest path from a single source to all nodes, detecting negative cyclesFinding shortest paths between all pairs of nodes
Optimal forDense graphs (with O(V^2) complexity) or sparse graphs with a priority queueGraphs with negative weightsDense graphs
InitializationInitializes distances to infinity except the source nodeInitializes distances to infinity except the source nodeInitializes the distance matrix with edge weights
RelaxationRelaxes all edges (V-1) timesRelaxes all edges (V-1) timesUpdates shortest paths considering each vertex as an intermediate vertex
Iteration Over EdgesUses a priority queue to pick the minimum distance vertexIterates over all edgesIterates over all pairs of nodes
Cycle DetectionNot applicableDetects negative weight cyclesNot applicable (can be used to detect negative cycles)
Algorithm TypeGreedyDynamic ProgrammingDynamic Programming

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible