기술나눔

플로이드의 알고리즘 - AcWing 343. 정렬

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

목차

플로이드 알고리즘

정의

용법

지침

문제 해결 아이디어

기본 단계

AcWing 343. 정렬

질문 설명

코드 실행

코드 아이디어

아이디어 개선

플로이드 알고리즘

정의

Floyd-Warshall 알고리즘의 전체 이름인 Floyd 알고리즘은 그래프의 모든 정점 쌍 사이의 최단 경로 문제를 해결하는 데 사용되는 동적 프로그래밍 알고리즘입니다. 가중치가 있는 방향 그래프에 적합하며 음의 가중치 간선을 처리할 수 있고(음의 가중치 주기를 포함하는 그래프는 제외) 그래프에 음의 가중치 주기가 있는지 여부를 감지할 수 있습니다.

용법

  1. 모든 정점 쌍 사이의 최단 경로를 계산합니다.: 소셜 네트워크 분석, 교통 네트워크 계획, 통신 네트워크 설계 등의 분야에서 플로이드 알고리즘은 두 지점 사이의 최단 거리를 계산해야 할 때 좋은 선택입니다.
  2. 음의 체중 주기 감지: 일부 응용 시나리오에서는 그래프에 음의 가중치 사이클이 없는지 확인해야 합니다. 이는 시스템의 일부 비정상 또는 오류 상태를 나타낼 수 있기 때문입니다.

지침

  • 메모리 소비 : 플로이드 알고리즘의 공간 복잡도는 O(n^2)입니다. 여기서 n은 그래프의 정점 수입니다. 대규모 그래프의 경우 이는 문제가 될 수 있습니다.
  • 시간 복잡도: Floyd 알고리즘의 시간복잡도는 O(n^3)입니다. 정점 개수가 많으면 알고리즘 속도가 매우 느려질 수 있습니다.
  • 음의 무게 루프 : 그래프에 음의 가중치 주기가 있으면 플로이드의 알고리즘은 무한 루프에 빠지게 됩니다. 노드에서 시작하면 이 주기를 통해 경로 길이가 무한히 줄어들 수 있기 때문입니다. 실제 적용에서는 이러한 상황을 먼저 감지하고 처리해야 합니다.
  • 알고리즘은 음의 체중 주기를 감지할 수 있습니다.알고리즘을 실행하는 동안 정점에서 정점까지의 최단 경로가 0보다 작은 것으로 확인되면, 즉 D[i][i] < 0이면 그래프에 적어도 하나의 음의 가중치 사이클이 있는 것입니다. 그리고 알고리즘은 현재로서는 올바른 최단 경로 결과를 제공할 수 없습니다.
  • 매우 큰 그래프의 경우 알고리즘의 높은 시간 복잡도와 공간 복잡도로 인해 병목 현상이 발생할 수 있습니다. 이때 보다 효율적인 알고리즘을 고려하거나 보다 전문적인 데이터 구조 및 최적화 기술을 사용해야 할 수도 있습니다.

문제 해결 아이디어

Floyd 알고리즘의 핵심 아이디어는 동적 프로그래밍이며, 기본 단계는 다음과 같습니다.

  1. 초기화: 거리 행렬 D를 그래프의 인접 행렬로 설정합니다. 즉, D[i][j] = Weight(i, j) for i != j, if (i, j)가 연결되지 않은 경우; D[i][ j] = 무한; D[i][i] = 0.
  2. 동적 프로그래밍: k = 1 ~ n에 대해 D[i][j] = min(D[i][j], D[i][k] + D[k][j])가 되도록 D를 업데이트합니다. i에서 j까지의 거리가 중간 노드 k를 통해 단축될 수 있는지 확인합니다.
  3. 결과: 최종 D 행렬에는 모든 정점 쌍 사이의 최단 경로 길이가 포함됩니다. 업데이트 과정에서 특정 D[i][j] < 0이고 i != j이고 D[i][i] < 0이 발생하면 그래프에 음의 가중치 주기가 있음을 의미합니다.

Floyd 알고리즘의 구현은 일반적으로 삼중 루프를 사용하여 모든 중간 정점 k를 통과하고 내부 두 루프는 더 짧은 경로가 있는지 확인하기 위해 모든 정점 쌍(i, j)을 통과합니다.

기본 단계

n개의 정점을 포함하는 가중치 그래프 G가 있다고 가정하면 2차원 배열을 사용할 수 있습니다.dist[][] 각 정점 쌍 사이의 최단 경로 길이를 저장합니다. 처음에는,dist[i][j]i와 j 사이에 직접 연결된 간선이 없으면 그래프에서 직접 연결된 간선의 가중치로 설정됩니다.dist[i][j]무한대로 설정합니다(도달할 수 없음을 나타냄).

  1. 초기화 : n×n 행렬 D를 생성합니다. 여기서 D[i][j]는 그래프의 i에서 j까지의 직접 가장자리의 가중치로 초기화되거나, i와 j 사이에 직접적인 가장자리가 없으면 무한대로 설정됩니다. 대각선 요소 D[i][i] = 0.

  2. 동적 프로그래밍 : 각 정점 k(중간 정점)에 대해 각 정점 i와 j 쌍 사이의 최단 경로를 업데이트합니다. k를 중간 지점으로 사용하여 더 짧은 경로를 얻을 수 있습니다. 업데이트 공식은 D[i][j] = min(D[i][j], D[i][k] + D[k][j])입니다. 이는 i에서 j까지의 경로가 k를 중간 정점으로 통해 짧아지면 D[i][j]를 업데이트한다는 의미입니다.

  3. 결과 출력: n회 반복 후에 행렬 D의 각 요소 D[i][j]는 i에서 j까지의 최단 경로 길이입니다.

AcWing 343. 정렬

질문 설명

343. 정렬 - AcWing 문제 은행

코드 실행

  1. #include <algorithm>
  2. #include <bits/stdc++.h>
  3. #include <iostream>
  4. using namespace std;
  5.  
  6. #define PII pair<int, int>
  7. #define fi first
  8. #define se second
  9. #define endl 'n'
  10. map<int, int> mp;
  11.  
  12. const int N = 210, mod = 1e9 + 7;
  13. int T, n, m, k;
  14. int a[N], dist[N][N];
  15. PII ans[N];
  16.  
  17. void floyd(int x) // 以 x 为中转点，更新其他点。
  18. {
  19.     for (int i = 1; i <= n; i++)
  20.         for (int j = 1; j <= n; j++)
  21.             dist[i][j] = min(dist[i][j], dist[i][x] + dist[x][j]);
  22. }
  23.  
  24. bool pd() // 判断是否所有点都已确定
  25. {
  26.     for (int i = 1; i <= n; i++) {
  27.         int cnt = 0;
  28.         for (int j = 1; j <= n; j++)
  29.             if (dist[i][j] != 1e9)
  30.                 cnt++; // 当前点能到达的点数
  31.         ans[i] = {cnt, i};
  32.         for (int j = 1; j <= n; j++)
  33.             if (i != j && dist[j][i] != 1e9)
  34.                 cnt++; // 能到达当前点的点数
  35.         if (cnt != n)
  36.             return 0;
  37.     }
  38.     sort(ans + 1, ans + n + 1);
  39.     return 1;
  40. }
  41.  
  42. int main() {
  43.     while (cin >> n >> m && n) {
  44.         for (int i = 1; i <= n; i++)
  45.             for (int j = 1; j <= n; j++)
  46.                 if (i != j)
  47.                     dist[i][j] = 1e9;
  48.  
  49.         int flag = 0;
  50.         for (int i = 1; i <= m; i++) {
  51.             char a, t, b;
  52.             cin >> a >> t >> b;
  53.             int x = a - 'A' + 1, y = b - 'A' + 1; // 现在要加一条从 y 到 x 的边
  54.  
  55.             if (!flag && dist[x][y] != 1e9) // 发现已经从x能到y，出现矛盾
  56.             {
  57.                 printf("Inconsistency found after %d relations.n", i);
  58.                 flag = 1;
  59.             }
  60.  
  61.             dist[y][x] = 1;
  62.             floyd(x), floyd(y); // 分别以 x 和 y 为中转点更新其他点
  63.             if (!flag && pd()) { // 发现所有点都已确定
  64.                 printf("Sorted sequence determined after %d relations: ", i);
  65.                 for (int i = 1; i <= n; i++)
  66.                     cout << char(ans[i].se + 'A' - 1);
  67.                 printf(".n");
  68.                 flag = 1;
  69.             }
  70.         }
  71.         if (!flag)
  72.             printf("Sorted sequence cannot be determined.n"); // 无法确定
  73.     }
  74.  
  75.     return 0;
  76. }

코드 아이디어

  1. 초기화: 사용하다dist2차원 배열은 무한대로 초기화됩니다. 이는 기본적으로 부등식 사이에 명확한 순서 관계가 없음을 의미합니다.
  2. 입력 읽기: B가 A보다 낫다는 것을 나타내는 "B &gt; A" 형식으로 표준 입력에서 관계를 읽습니다.
  3. 관계 처리:
    • 새로운 관계를 읽어오면 모순이 있는지(즉, 이전에 결정된 관계가 새로운 관계와 충돌하는지) 검사한다.
    • 고쳐 쓰다dist플로이드의 알고리즘을 사용하여 모든 불평등 사이의 최단 경로를 업데이트하는 매트릭스는 실제로 "우선순위" 또는 "순서" 관계를 업데이트하는 것입니다.
  4. 정렬 확실성 확인:
    • 모든 불평등이 관련되어 있는지 확인하십시오. 즉, 모든 점이 다른 모든 점에 도달할 수 있고 경로 길이가 무한하지 않은지 확인하십시오.
    • 관계를 읽는 과정에서 정렬이 발견되거나, 모든 관계를 읽어도 여전히 정렬을 결정할 수 없는 경우 해당 정보가 출력됩니다.

아이디어 개선

  • 효율성 향상 : 현재 플로이드 호출은 각각의 새로운 관계가 추가된 직후에 이루어지며 이는 필요하지 않을 수도 있습니다. 불필요한 계산을 줄이기 위해 Floyd 알고리즘을 다시 수행하기 전에 모든 관계를 읽을 때까지 기다릴 수 있습니다.
  • 논리를 단순화하라 : 현재 코드는 모순을 감지하고 정렬 완료 논리를 결정하는 데 더 복잡합니다. 보다 직관적인 데이터 구조나 알고리즘 단계를 사용하여 이러한 조건을 확인하는 등 논리를 단순화할 수 있습니다.
  • 코드 명확성: 주석과 코드 구조의 명확성을 높여 코드를 더 쉽게 이해하고 유지 관리할 수 있습니다.

개인 프로필

그는 30년 이상 기술 연구에 전념해 왔으며, java, linux, javascript, php, css 등 다양한 언어에 능숙하며, 오픈 소스 분야에 많은 공헌을 했습니다. 나중에 참조할 수 있도록 기술 개발의 일부 문제를 공유하는 개발자 문서 스테이션입니다.

내 연락처 정보

우편