Advanced Algorithm Design · Algorithm Design

Floyd-Warshall DP View

Students revisit all-pairs shortest paths as a dynamic programming pattern based on which intermediate vertices are allowed.

Enroll Now Text Us Contact Code Scholars Full DSA Course

Student Focus

This optional page connects two major topics for students preparing for college algorithms.

Guided Lesson Notes

Understanding Floyd-Warshall DP View

Floyd-Warshall DP View focuses on overlapping subproblems, reusable answers, and turning recursion into a table or memo. Students revisit all-pairs shortest paths as a dynamic programming pattern based on which intermediate vertices are allowed.

Model: define one state as a smaller question whose answer can help build larger answers.

Invariant: when a state is used, every smaller state it depends on must already be correct or memoized.

Implementation: state definitions, recurrence formulas, base cases, table order, memoization maps, and reconstruction when needed.

Use Floyd-Warshall DP View when the problem asks for best, count, longest, shortest, ways, or choices over prefixes, positions, capacities, or subsets.

Visual Model

A small picture for Floyd-Warshall DP View

0123012301230123012301230

Key Ideas

Intermediate-vertex state
Distance matrix updates
Graph DP perspective

Practice Prompts

Explain the recurrence in words.
Compare this DP view with repeated single-source shortest paths.

Vocabulary

Terms students should be able to say clearly

State

A smaller subproblem described by indexes, capacity, mask, or other parameters.

Recurrence

The formula that builds one state from smaller states.

Base case

A state whose answer is known immediately.

Memoization

Top-down caching of recursive answers.

Tabulation

Bottom-up filling of a table.

Transition

One possible move from previous states into the current state.

Worked Example

Worked example: tracing Floyd-Warshall DP View

Trace a small input, focusing on intermediate-vertex state.

1Write a small input where Floyd-Warshall DP View is clearly useful.
2Label the part of the input related to Intermediate-vertex state.
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
Trace a small input	Small n	Use a tiny example to understand state changes before coding.
Implement the core idea	Depends on topic	Choose data structures that match the operations you need.
Analyze growth	Big-O	Explain how work changes as the input gets larger.

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 DP View 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 DP View: 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