Graphs 0/61

Dijkstra and shortest paths · 4 of 4

Floyd-Warshall

Compute the distance between every pair of vertices with three loops over a table, and choose among this lesson's methods.

1,975 words · 9 min read

Part 1 of 6 All pairs of vertices

Distances between all pairs of vertices

Dijkstra's algorithm and Bellman-Ford both find the distances from one source. Some problems ask for the distance between many different pairs of vertices:

There are nn cities and mm two-way roads with lengths. Answer qq queries, each asking for the length of the shortest route between two cities, or -1 if there is none.

The first line has nn, mm and qq. Then come the roads as aa, bb and cc, and the queries as aa and bb.

Constraints

  • 1≤n≤5001 \le n \le 500
  • 1≤m≤n21 \le m \le n^2
  • 1≤q≤1051 \le q \le 10^5
  • 1≤a,b≤n1 \le a, b \le n
  • 1≤c≤1091 \le c \le 10^9

Sample · Input

4 3 5
1 2 5
1 3 9
2 3 3
1 2
2 1
1 3
1 4
3 2

Output

5
5
8
-1
3

In the sample the shortest route from city 1 to city 3 goes through city 2 and has length 5+3=85 + 3 = 8, less than the direct road of length 9. No road leads to city 4, so the fourth query is answered with −1-1.

There can be 10510^5 queries and only 500 cities, so it pays to compute the distance between every pair of cities once, keep the 500×500500 \times 500 distances in a table, and answer each query by looking it up. We could fill the table by running Dijkstra's algorithm from each city in turn. The Floyd-Warshall algorithm is shorter to write, three nested loops and no heap, and unlike Dijkstra's algorithm it also works when some weights are negative, as long as no cycle has weights that add up to less than 0.