c++/ 자료구조&알고리즘 개념 복습하기 - 22 / 플로이드 워셜 알고리즘

< 플로이드 워셜 >

• 모든 정점 쌍 사이의 최단거리를 구하는 알고리즘
• 각 정점을 거쳐서 가능 경우를 생각한다
  i->j 로 가는 과정에서 정점A를 거쳐가는게 더 빠르다면 최단 거리를 업데이트 해준다
  
• 각 정점 별로 모든 정점의 쌍을 검사하므로 O(n^3) 시간 복잡도
  ( n(정점 수) * n^2(정점의 쌍) )

int INF = 1000000;

int a[4][4] = {
  { 0, 5, INF, 8 },
  { 7, 0, 9, INF },
  { 2, INF, 0, 4 },
  { INF, INF, 3, 0 }
};

for(int i = 0; i < 4; i++) { // 자기자신으로 가는 것은 0
	a[i][i] = 0;
}

// 시간복잡도 O(V^3)
for(int k = 0; k < 4; k++)  // k : 거쳐가는 정점
  for(int i = 0; i < 4; i++)  // i = 출발 정점
    for(int j = 0; j < 4; j++)  // j = 도착 정점
      if (a[i][k] + a[k][j] < a[i][j]) {
        a[i][j] = a[i][k] + a[k][j];
      }
   
// 점화식  
// distance[i,j] = 
// min(distance[i,j], distance[i,n] + distance[n,j])

< 경로 정보 저장하기 >

• 최단 거리 업데이트 하면서 경로 정보도 같이 업데이트한다!
• i에서 j로 가는 최단 거리에서 먼저 거처야 하는 정점을 저장하는 배열을 생성!

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
    int INF = 1000000;

    int a[5][5] = {
        {0, 4, 1, 1, INF},
        {4, 0, INF, INF, 8},
        {1, INF, 0, 3, 15},
        {1, INF, 3, 0, 6},
        {INF, 8, 15, 6, 0}
    };

    // i -> j로 최단 경로로 갈때 어느 정점을 먼저 들러야 하는지 저장하는 배열! 
    // (정점 번호 : 1~5)
    int route[5][5] = {
        {0, 2, 3, 4, 0},
        {1, 0, 0, 0, 5},
        {1, 0, 0, 4, 5},
        {1, 0, 3, 0, 5},
        {0, 2, 3, 4, 0}
    };

    for (int i = 0; i < 5; i++)
    { // 자기자신으로 가는 것은 0
        a[i][i] = 0;
    }

    // 시간복잡도 O(V^3)
    for (int k = 0; k < 5; k++)
    { // k : 거쳐가는 정점
        for (int i = 0; i < 5; i++)
        { // i = 출발 정점
            for (int j = 0; j < 5; j++)
            { // j = 도착 정점
                if (a[i][k] + a[k][j] < a[i][j])
                {
                    a[i][j] = a[i][k] + a[k][j];
                    route[i][j] = route[i][k]; 
                    // k를 거쳐가는게 최단거리라면 i 에서 k를 가기위해 들르는 정점 정보 할당!
                }
            }
        }
    }

    for(int i = 0; i < 5; i++) {
        for(int j = 0; j < 5; j++) {
            cout << route[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}