2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Inhaltsverzeichnis
Der Floyd-Algorithmus, der vollständige Name des Floyd-Warshall-Algorithmus, ist ein dynamischer Programmieralgorithmus, der zur Lösung des Problems des kürzesten Pfades zwischen allen Scheitelpunktpaaren im Diagramm verwendet wird. Es eignet sich für gewichtete gerichtete Diagramme und kann negative Gewichtskanten verarbeiten (jedoch keine Diagramme mit negativen Gewichtszyklen) und kann erkennen, ob das Diagramm negative Gewichtszyklen enthält.
Die Kernidee des Floyd-Algorithmus ist die dynamische Programmierung. Die grundlegenden Schritte sind wie folgt:
Die Implementierung des Floyd-Algorithmus verwendet normalerweise eine Dreifachschleife. Die äußere Schleife durchläuft alle Zwischenscheitelpunkte k und die inneren beiden Schleifen durchlaufen alle Scheitelpunktpaare (i, j), um zu prüfen, ob es einen kürzeren Pfad gibt.
Angenommen, wir haben einen gewichteten Graphen G mit n Eckpunkten, dann können wir ein zweidimensionales Array verwendendist[][]
um die kürzeste Pfadlänge zwischen jedem Scheitelpunktpaar zu speichern. Anfänglich,dist[i][j]
wird auf das Gewicht der direkt verbundenen Kante im Diagramm gesetzt. Wenn es keine direkt verbundene Kante zwischen i und j gibt, danndist[i][j]
Auf unendlich eingestellt (was bedeutet, dass es nicht erreichbar ist).
Initialisierung : Erstellen Sie eine n×n-Matrix D, wobei D[i][j] mit dem Gewicht der direkten Kante von i nach j im Diagramm initialisiert oder auf unendlich gesetzt wird, wenn es keine direkte Kante zwischen i und j gibt. Diagonalelement D[i][i] = 0.
dynamische Programmierung : Aktualisieren Sie für jeden Scheitelpunkt k (als Zwischenscheitelpunkt) den kürzesten Pfad zwischen jedem Scheitelpunktpaar i und j. Es ist möglich, einen kürzeren Pfad mit k als Zwischenpunkt zu erhalten. Die Aktualisierungsformel lautet: D[i][j] = min(D[i][j], D[i][k] + D[k][j]). Das heißt, wenn der Weg von i nach j über k als Zwischenscheitelpunkt kürzer wird, aktualisieren Sie D[i][j].
Ergebnisausgabe: Nach n Iterationsrunden ist jedes Element D[i][j] in der Matrix D die kürzeste Pfadlänge von i nach j.
343. Sortieren – AcWing-Fragenbank
- #include <algorithm>
- #include <bits/stdc++.h>
- #include <iostream>
- using namespace std;
-
- #define PII pair<int, int>
- #define fi first
- #define se second
- #define endl 'n'
- map<int, int> mp;
-
- const int N = 210, mod = 1e9 + 7;
- int T, n, m, k;
- int a[N], dist[N][N];
- PII ans[N];
-
- void floyd(int x) // 以 x 为中转点,更新其他点。
- {
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= n; j++)
- dist[i][j] = min(dist[i][j], dist[i][x] + dist[x][j]);
- }
-
- bool pd() // 判断是否所有点都已确定
- {
- for (int i = 1; i <= n; i++) {
- int cnt = 0;
- for (int j = 1; j <= n; j++)
- if (dist[i][j] != 1e9)
- cnt++; // 当前点能到达的点数
- ans[i] = {cnt, i};
- for (int j = 1; j <= n; j++)
- if (i != j && dist[j][i] != 1e9)
- cnt++; // 能到达当前点的点数
- if (cnt != n)
- return 0;
- }
- sort(ans + 1, ans + n + 1);
- return 1;
- }
-
- int main() {
- while (cin >> n >> m && n) {
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= n; j++)
- if (i != j)
- dist[i][j] = 1e9;
-
- int flag = 0;
- for (int i = 1; i <= m; i++) {
- char a, t, b;
- cin >> a >> t >> b;
- int x = a - 'A' + 1, y = b - 'A' + 1; // 现在要加一条从 y 到 x 的边
-
- if (!flag && dist[x][y] != 1e9) // 发现已经从x能到y,出现矛盾
- {
- printf("Inconsistency found after %d relations.n", i);
- flag = 1;
- }
-
- dist[y][x] = 1;
- floyd(x), floyd(y); // 分别以 x 和 y 为中转点更新其他点
- if (!flag && pd()) { // 发现所有点都已确定
- printf("Sorted sequence determined after %d relations: ", i);
- for (int i = 1; i <= n; i++)
- cout << char(ans[i].se + 'A' - 1);
- printf(".n");
- flag = 1;
- }
- }
- if (!flag)
- printf("Sorted sequence cannot be determined.n"); // 无法确定
- }
-
- return 0;
- }
dist
Das zweidimensionale Array wird auf unendlich initialisiert, was bedeutet, dass es standardmäßig keine eindeutige Ordnungsbeziehung zwischen den Ungleichungen gibt.dist
Matrix verwendet den Floyd-Algorithmus, um den kürzesten Weg zwischen allen Ungleichungen zu aktualisieren. Hier wird tatsächlich die „Prioritäts“- oder „Reihenfolge“-Beziehung aktualisiert.