CodeBlanks Logo Icon CodeBlanks
Login Register

All pairs

Shortest path between every pair of vertices.

All pairs

The Floyd-Warshall algorithm finds the shortest paths between all pairs of nodes in a graph in one go. The output is a distance matrix.

It returns results for all pairs, not just a single source. This is useful in dense graph problems.

Distance matrix

The graph is represented as an n×n adjacency matrix. graph[i][j] is the direct edge weight from i to j; if no edge, 999 (infinity) is used.

The diagonal is zero: graph[i][i] = 0. A triple loop runs on the matrix to compute the shortest paths.

Practice init_graph function

Write init_graph(). Return the 4×4 adjacency matrix. Print it with print(init_graph()).

Starter code

solution.py
def init_graph():
    # Return adjacency matrix

Sample solution

solution.py
def init_graph():
    # Return adjacency matrix
    return [[0, 3, 999, 7], [999, 0, 1, 999], [999, 999, 0, 2], [999, 4, 999, 0]]
print(init_graph())

Expected output

[[0, 3, 999, 7], [999, 0, 1, 999], [999, 999, 0, 2], [999, 4, 999, 0]]

Questions and answers

Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.

1 How many node pairs does Floyd-Warshall solve?

  • All pairs Correct answer
  • Single source
  • Only one pair
  • Only neighbors

Explanation: Floyd-Warshall solves all pairs.

2 Infinity value

Question 
graph[i][j] = ____ (if no edge)
Answer 
graph[i][j] = 999 (if no edge)

Explanation: 999 is right.

3 All pairs: match the terms

Term Meaning
graph[i][i] 0
graph[i][j] Edge
999 Infinity
n×n Size

All lessons in Advanced

1 DP - Memoization

  1. What is memoization?
  2. Fibonacci memoization
  3. Dict-based cache
  4. Summary - Memoization

2 DP - Tabulation

  1. What is tabulation?
  2. Building the table
  3. Fibonacci tabulation
  4. Summary - Tabulation

3 LCS

  1. LCS definition
  2. DP table
  3. Backtracking the table
  4. Summary - LCS

4 Knapsack

  1. Knapsack problem
  2. 0/1 knapsack DP
  3. Decision table
  4. Summary - Knapsack

5 DP project

  1. Project: Overview
  2. Cost table
  3. DP solution
  4. Print the result

6 Matrix chain

  1. Multiplication order
  2. DP table
  3. Split point
  4. Summary - Matrix chain

7 Floyd-Warshall

  1. All pairs
  2. Triple loop
  3. Table update
  4. Summary - Floyd-Warshall

8 Dijkstra

  1. Single source
  2. Priority queue
  3. Relaxation
  4. Summary - Dijkstra

9 Bellman-Ford

  1. Negative weights
  2. Edge relaxation loop
  3. Negative cycle
  4. Summary - Bellman-Ford

10 Kruskal

  1. Minimum spanning tree
  2. Edge sorting
  3. Cycle check
  4. Summary - Kruskal

11 Prim

  1. Prim idea
  2. Priority queue
  3. Visited set
  4. Summary - Prim

12 Topological sort

  1. Dependency order
  2. DFS-based sort
  3. Kahn algorithm
  4. Summary - Topological sort

13 Union-find, trie, segment tree

  1. Union-find
  2. Trie
  3. Segment tree
  4. Summary - Advanced structures

14 Advanced final

  1. Challenge 1
  2. Challenge 2
  3. Challenge 3
  4. Challenge 4