content/graph/floydWarshall.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

vector<vector<ll>> dist; // Entfernung zwischen je zwei Punkten.
vector<vector<int>> next;

void floydWarshall() {
	next.assign(ssize(dist), vector<int>(ssize(dist), -1));
	for (int i = 0; i < ssize(dist); i++) {
		for (int j = 0; j < ssize(dist); j++) {
			if (dist[i][j] < INF) {
				next[i][j] = j;
	}}}

	for (int k = 0; k < ssize(dist); k++) {
		for (int i = 0; i < ssize(dist); i++) {
			for (int j = 0; j < ssize(dist); j++) {
				// only needed if dist can be negative
				if (dist[i][k] == INF || dist[k][j] == INF) continue;
				if (dist[i][j] > dist[i][k] + dist[k][j]) {
					dist[i][j] = dist[i][k] + dist[k][j];
					next[i][j] = next[i][k];
}}}}}

vector<int> getPath(int u, int v) {
	if (next[u][v] < 0) return {};
	vector<int> path = {u};
	while (u != v) path.push_back(u = next[u][v]);
	return path; //Pfad u -> v
}