플로이드 알고리즘

[devLupin]

• i 정점에서 j 정점까지의 모든 최단 경로를 찾는 문제
• $O(N^3)$에 해결

for(int k=1; k<=n; k++) 
    for(int i=1; i<=n; i++) 
        for(int j=1; j<=n; j++) 
            arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);

[devLupin]

• 경로를 불러오는 방법

  • 초기에는 a->b를 b로 저장
  • 상기 플로이드 최단 경로를 구하는 과정에서 값의 갱신이 일어날 때, 경로 배열도 변경된다.

  while(m--) {
      cin >> a >> b >> c;    // 정점 a에서 b로 가는 비용이 c
      nxt[a][b] = b;
  }
  
  for(int k=1; k<=n; k++)
      for(int i=1; i<=n; i++)
          for(int j=1; j<=n; j++) {
              if(arr[i][j] > arr[i][k] + arr[k][j]) {    // 최단 경로 및 경로 저장
                  arr[i][j] = arr[i][k] + arr[k][j];
                  nxt[i][j] = nxt[i][k];
              }
          }
  
  for(int i=1; i<=n; i++) {
      for(int j=1; j<=n; j++) {
          if(arr[i][j] == 0 || arr[i][j] == INF) {  // i==j 이거나 길이 없는 경우
              cout << "0\n";
              continue;
          }
  
          vector<int> path;
          int cur = i;
          while(cur != j) {
              path.push_back(cur);
              cur = nxt[cur][j];
          }
          path.push_back(j);
      }
  }