Graphs and Network Algorithms · Shortest Paths

Floyd-Warshall Algorithm

Floyd-Warshall computes all-pairs shortest paths by gradually allowing more intermediate vertices.

Enroll Now Text Us Contact Code Scholars Full DSA Course

Student Focus

This topic links graph algorithms with dynamic programming in a compact way.

Guided Lesson Notes

Understanding Floyd-Warshall Algorithm

Floyd-Warshall Algorithm focuses on relationships, reachability, paths, cycles, connectivity, and optimization over edges. Floyd-Warshall computes all-pairs shortest paths by gradually allowing more intermediate vertices.

Model: draw vertices as dots and edges as connections; then decide whether direction, weight, or capacity matters.

Invariant: visited, distance, parent, component, or flow arrays must match what has actually been discovered so far.

Implementation: adjacency lists or matrices, queues, stacks, priority queues, union-find, and repeated edge relaxation.

Use Floyd-Warshall Algorithm when the problem mentions roads, networks, prerequisites, components, shortest paths, spanning costs, or dependency order.

Visual Model

A small picture for Floyd-Warshall Algorithm

Key Ideas

All-pairs distances
Dynamic programming table
Intermediate-vertex updates

Practice Prompts

Update a small distance matrix by hand.
Compare single-source and all-pairs shortest-path needs.

Vocabulary

Terms students should be able to say clearly

Vertex

An object or state in the graph.

Edge

A relationship or move between vertices.

Path

A sequence of edges from one vertex to another.

Cycle

A path that returns to a previous vertex.

Component

A group of vertices connected by reachability.

Relaxation

Trying to improve a known distance or cost through an edge.

Worked Example

Worked example: tracing Floyd-Warshall Algorithm

Trace a small input, focusing on all-pairs distances.

1Write a small input where Floyd-Warshall Algorithm is clearly useful.
2Label the part of the input related to All-pairs distances.
3Perform one operation and explain which invariant is still true afterward.
4Run a second operation that touches an edge case, such as an empty side, duplicate value, boundary index, disconnected vertex, or tie.
5Finish by saying which operation dominates the runtime and why.

Complexity Check

Costs students should be able to explain

Operation	Typical Cost	Reason
Adjacency-list traversal	O(V + E)	DFS and BFS visit vertices and inspect edges.
Adjacency matrix storage	O(V^2)	A matrix reserves space for every possible pair.
Weighted optimization	Varies	MST and shortest-path algorithms depend on sorting, heaps, and graph density.

Common Mistakes

What to watch while practicing

Coding before drawing the structure or state changes.
Forgetting the invariant that makes the algorithm correct.
Testing only the sample input and skipping boundary cases.
Giving Big-O without explaining which operation dominates the work.

Interview-Style Coding Problem

Floyd-Warshall Algorithm interview problem: City With Fewest Reachable Neighbors

Interview medium-hard

Problem

Given an undirected weighted graph and a distance threshold, return the city that can reach the fewest other cities within the threshold. Break ties by choosing the larger city index.

Input

The first line contains n, m, and threshold. The next m lines contain edges u v w using 0-based city labels.

Output

Print the chosen city index.

Sample Input

Sample Output

Why the sample works

Cities 0 and 3 each reach two cities within distance 4, so the larger index 3 is chosen.

Approach

1Initialize an all-pairs distance matrix.
2Run Floyd-Warshall to consider every city as a middle point.
3Count how many other cities are within the threshold for each city.
4Update the answer on a smaller count, or on a tie with a larger index.

O(n^3) time and O(n^2) extra space.

Java Solution

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int threshold = sc.nextInt();

    int inf = 1_000_000_000;
    int[][] dist = new int[n][n];
    for (int i = 0; i < n; i++) {
      Arrays.fill(dist[i], inf);
      dist[i][i] = 0;
    }

    for (int i = 0; i < m; i++) {
      int u = sc.nextInt();
      int v = sc.nextInt();
      int w = sc.nextInt();
      dist[u][v] = Math.min(dist[u][v], w);
      dist[v][u] = Math.min(dist[v][u], w);
    }

    for (int mid = 0; mid < n; mid++) {
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          if (dist[i][mid] + dist[mid][j] < dist[i][j]) {
            dist[i][j] = dist[i][mid] + dist[mid][j];
          }
        }
      }
    }

    int answer = -1;
    int bestCount = Integer.MAX_VALUE;
    for (int city = 0; city < n; city++) {
      int count = 0;
      for (int other = 0; other < n; other++) {
        if (city != other && dist[city][other] <= threshold) count++;
      }
      if (count <= bestCount) {
        bestCount = count;
        answer = city;
      }
    }

    System.out.println(answer);
  }
}

Python Solution

n, m, threshold = map(int, input().split())
INF = 10 ** 12
dist = [[INF] * n for _ in range(n)]
for i in range(n):
    dist[i][i] = 0

for _ in range(m):
    u, v, w = map(int, input().split())
    dist[u][v] = min(dist[u][v], w)
    dist[v][u] = min(dist[v][u], w)

for mid in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][mid] + dist[mid][j] < dist[i][j]:
                dist[i][j] = dist[i][mid] + dist[mid][j]

answer = -1
best_count = 10 ** 9
for city in range(n):
    count = sum(1 for other in range(n) if city != other and dist[city][other] <= threshold)
    if count <= best_count:
        best_count = count
        answer = city

print(answer)

Practice Challenge

Make the idea your own

Create a two-minute explanation of Floyd-Warshall Algorithm: define it, trace one example, name one edge case, and give the runtime of the main operation.

Tutoring Connection

Need help with this topic?

Bring a question or code attempt to a tutoring session.

Reserve a Free Session Text Us Open Online Compiler