Course contentsShow
← Computer Science
Lesson 991 of 2,87223. Shortest Path AlgorithmsFree lesson

Floyd-Warshall Core Idea

The fundamental concept of considering intermediate vertices to find shortest paths between all pairs.

Floyd-Warshall Core Idea

What You'll Learn

You'll understand how the Floyd-Warshall algorithm considers intermediate vertices to find shortest paths between all pairs of vertices in a graph.

The Core Concept

Unlike Dijkstra's or Bellman-Ford, which focus on shortest paths from a single source, Floyd-Warshall solves the all-pairs shortest paths problem—finding the shortest path between every pair of vertices simultaneously.

The brilliant insight is simple: What if we could improve a path from vertex i to vertex j by routing it through some intermediate vertex k?

Building Paths Through Intermediate Vertices

Imagine you want to travel from city A to city Z. Initially, you only consider direct routes. But what if going through city M creates a shorter path?

Floyd-Warshall systematically asks: "For every pair of vertices (i, j), can we find a shorter path by using vertex k as an intermediate stop?"

The algorithm considers vertices as potential intermediates one at a time:

  • First, try routing paths through vertex 0
  • Then, try routing through vertices {0, 1}
  • Then through vertices {0, 1, 2}
  • And so on...

For each intermediate vertex k, we check every pair (i, j) and ask: is distance[i][k] + distance[k][j] shorter than our current distance[i][j]?

Why This Works

By progressively allowing more vertices as intermediates, we build up optimal paths. When we finish considering all vertices as potential intermediate stops, we've found the shortest path between every pair—using any combination of intermediate vertices.

Key Takeaway: Floyd-Warshall's core idea is to systematically improve all pairwise shortest paths by considering each vertex as a potential intermediate waypoint, one vertex at a time.