내 연락처 정보
우편메소피아@프로톤메일.com
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
목차
Floyd-Warshall 알고리즘의 전체 이름인 Floyd 알고리즘은 그래프의 모든 정점 쌍 사이의 최단 경로 문제를 해결하는 데 사용되는 동적 프로그래밍 알고리즘입니다. 가중치가 있는 방향 그래프에 적합하며 음의 가중치 간선을 처리할 수 있고(음의 가중치 주기를 포함하는 그래프는 제외) 그래프에 음의 가중치 주기가 있는지 여부를 감지할 수 있습니다.
Floyd 알고리즘의 핵심 아이디어는 동적 프로그래밍이며, 기본 단계는 다음과 같습니다.
Floyd 알고리즘의 구현은 일반적으로 삼중 루프를 사용하여 모든 중간 정점 k를 통과하고 내부 두 루프는 더 짧은 경로가 있는지 확인하기 위해 모든 정점 쌍(i, j)을 통과합니다.
n개의 정점을 포함하는 가중치 그래프 G가 있다고 가정하면 2차원 배열을 사용할 수 있습니다.dist[][]
각 정점 쌍 사이의 최단 경로 길이를 저장합니다. 처음에는,dist[i][j]
i와 j 사이에 직접 연결된 간선이 없으면 그래프에서 직접 연결된 간선의 가중치로 설정됩니다.dist[i][j]
무한대로 설정합니다(도달할 수 없음을 나타냄).
초기화 : n×n 행렬 D를 생성합니다. 여기서 D[i][j]는 그래프의 i에서 j까지의 직접 가장자리의 가중치로 초기화되거나, i와 j 사이에 직접적인 가장자리가 없으면 무한대로 설정됩니다. 대각선 요소 D[i][i] = 0.
동적 프로그래밍 : 각 정점 k(중간 정점)에 대해 각 정점 i와 j 쌍 사이의 최단 경로를 업데이트합니다. k를 중간 지점으로 사용하여 더 짧은 경로를 얻을 수 있습니다. 업데이트 공식은 D[i][j] = min(D[i][j], D[i][k] + D[k][j])입니다. 이는 i에서 j까지의 경로가 k를 중간 정점으로 통해 짧아지면 D[i][j]를 업데이트한다는 의미입니다.
결과 출력: n회 반복 후에 행렬 D의 각 요소 D[i][j]는 i에서 j까지의 최단 경로 길이입니다.
- #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
2차원 배열은 무한대로 초기화됩니다. 이는 기본적으로 부등식 사이에 명확한 순서 관계가 없음을 의미합니다.dist
플로이드의 알고리즘을 사용하여 모든 불평등 사이의 최단 경로를 업데이트하는 매트릭스는 실제로 "우선순위" 또는 "순서" 관계를 업데이트하는 것입니다.