Purpose
Finds the shortest distances between all pairs of vertices in a weighted directed graph. Assumes no negative cycles.
Time Complexity
Depends
Usage
auto res = warshallfloyd(g);Get the distance from vertex s to e using res.dist[s][e]. Get the next vertex to visit to reach e from s via the shortest path using res.next[s][e].
Implementation
struct warshallfloyd_return { vector<vector<int>> dist, next;};warshallfloyd_return warshallfloyd(DirectedGraph &_g) { vector<vector<int>> dist(_g.n, vector<int>(_g.n, INF)), next(_g.n, vector<int>(_g.n, INF)); for (int i = 0; i < _g.n; i++) dist[i][i] = 0; for (int i = 0; i < _g.n; i++) for (int j = 0; j < _g.n; j++) next[i][j] = j; for (int i = 0; i < _g.n; i++) for (auto &j : _g.g[i]) chmin(dist[i][j.to], j.cost); for (int k = 0; k < _g.n; k++) for (int i = 0; i < _g.n; i++) for (int j = 0; j < _g.n; j++) if (chmin(dist[i][j], dist[i][k] + dist[k][j])) next[i][j] = next[i][k]; return {dist, next};}