Summary - Floyd-Warshall

Run Floyd-Warshall on a small graph in a mini task.

Summary - Floyd-Warshall

In this group you learned Floyd-Warshall, which finds shortest paths for all pairs. Adjacency matrix, triple loop and relaxation formula combine into the solution.

Now you will write a query function that brings all pieces together. This summary unites the group's concepts in a single piece of code.

Exercise shortest_distance function

Write shortest_distance(graph, src, dst). Run Floyd-Warshall, return dist[src][dst]. Print 6 with print(shortest_distance(init_graph(), 0, 3)).

Show example solution

def shortest_distance(graph, src, dst):
    # Solve all pairs and return src→dst
    n = len(graph)
    dist = [row[:] for row in graph]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist[src][dst]
print(shortest_distance(init_graph(), 0, 3))

Test yourself

What is the output of Floyd-Warshall?
- A single distance
- Edge weights
- A path list
- All-pairs distance matrix
Show answer

All-pairs distance matrix — The output is the all-pairs distance matrix.

Matrix copy

dist = [row[:] for row in ____]

Show answer

dist = [row[:] for row in graph]

Summary - Floyd-Warshall: match the terms

init_graph

Graph
relax_edge

Relaxation
floyd_warshall

Triple loop
dist

Distance

Next lesson: Single source

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies