(C++) 플로이드 와샬 Floyd Warshall (+ 최단 경로 알고리즘 비교)

👩🏼 플로이드 와샬 알고리즘

다익스트라 알고리즘과 같이 최단 거리를 구할 수 있는 알고리즘이다.

원리

• 다익스트라 알고리즘
  • 출발지 정점을 하나 정해놓고 그곳에서부터 다른 모든 정점으로의 최단 경로를 구한다.
  • 가장 적은 비용을 하나씩 선택해나간다. (우선순위 큐 사용)
• 플로이드 와샬 알고리즘
  • 모든 정점에서 모든 정점으로의 최단 경로를 한번에 구한다. 즉 정점과 정점, 모든 쌍의 최단 경로를 구하게 된다.
    • 모든 쌍을 표현하는 행렬(이차원 배열)을 선언하고 다이나믹 프로그래밍 방식으로 각각의 원소들(각 쌍의 최단거리)을 업데이트 해나간다.
      • 업데이트 기준 👉 현재 거쳐가는 정점
  • 거쳐가는 정점을 기준으로 알고리즘을 수행한다.
    • i 에서 j 로 가는데 해당 정점을 경유해서 가는 것이 더 빠르다면 그 정점을 거쳐서 가는걸로 업데이트 한다.

플로이드 와샬의 시각적인 진행 과정은 나동빈님 블로그에서 참고하기.

• i행과 j열의 원소인 (i, j) 원소는 정점i로부터 정점j까지의 최단 경로를 뜻한다.
• Dynamic Programming 방식으로 진행된다.
  • 점화식 👉 distance[i,j] = min(distance[i,j], distance[i,n] + distance[n,j])
    • 정점 i에서 정점 n을 거쳐서 정점 j로 갈 때, n을 거쳐 가는 것이 더 최단경로일 경우 업데이트 한다.
    • 이렇게 거쳐갈 정점을 차례대로 모두 검사하여 업데이트 해나간다.

• 행렬 초기화
  • 그래프 모양을 참고하여 초기화 한다.
  • 직접적으로 인접하여 연결되어 있지 않은 정점들의 경우 INF 무한대로 초기화 한다.
  • 자기 자신과 자기 자신이 연결되어 있진 않기 때문에 행렬의 대각선은 모두 0 이 된다.
• 거쳐갈 정점들을 처음부터 차례대로 검사하여 해당 정점을 거쳐 가는 것이 더 최단 경로일 경우 원소를 업데이트 한다. 매번 행렬 전체 원소들에 대해 진행!!
  • ex)
    • 정점 1 을 거쳐갈 때
      • 기존의 (i, j) 원소값 보다 (i, 1) + (1 + j) 값이 더 작으면 이 값으로 업데이트. 아니면 냅두기.
      • 즉 ! 정점 1 을 거쳐가는게 더 최단 경로일 경우 업데이트 하는 것이다.
    • 정점 2 을 거쳐갈 때
      • 기존의 (i, j) 원소값 보다 (i, 2) + (2 + j) 값이 더 작으면 이 값으로 업데이트. 아니면 냅두기.
      • 기존의 (i, j)는 정점 1 을 거쳐오는 경우도 고려해서 최단 경로를 업데이트 기존에 됐던 경우다.
      • 정점 2 을 거쳐가는게 더 최단 경로일 경우 업데이트 하고 아니라면 정점 2 거쳐가지 말고 기존 값 그대로 냅두기 !
    • 이런식으로 모든 정점을 거쳐가는 경우를 쭉쭉 따져서 전체 행렬 원소들을 업데이트 해나가면 된다.

코드

코드 출처 나동빈님 블로그

플로이드 와샬 알고리즘 코드는 굉장히 간단하다.

int INF = 1000000;

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

// 시간복잡도 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])  // 점화식 distance[i,j] = min(distance[i,j], distance[i,n] + distance[n,j])
        a[i][j] = a[i][k] a[k][j];

응용 코드

프로그래머스 ‘순위’ 문제 풀이

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    
    vector<vector<bool>> graph(n + 1, vector<bool>(n + 1));
    
    for(int i = 0; i < results.size(); i++)
        graph[results[i][0]][results[i][1]] = true;
    
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if (graph[i][k] == true && graph[k][j] == true)
                    graph[i][j] = true;
    
    for(int i = 1; i <= n; i++)
    {
        int count = 0;
        for(int j = 1; j <= n; j++)
            if (graph[i][j] == true || graph[j][i] == true)
                count++;
        if (count == n - 1)
            answer++;
    }
    
    return answer;
}

    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if (graph[i][k] == true && graph[k][j] == true)
                    graph[i][j] = true;

(i, j) 원소는 i 선수가 j 선수를 이길 수 있느냐에 대한 bool 값이다. i 선수가 n선수를 거쳐서도 j 선수를 이길 수 있는게 확실하다면 원소 값을 True로 설정한다. 확실하지 않다면 기존 값으로 냅둔다. 즉 선수 n을 통해(경유해서) 승리를 확신할 수 있게 된 경우엔 True로 업데이트 해준다. False로 갱신되는 경우는 없음!! (경유 할 수 없으면 False로 바꿔야 하나 하고 혼란스러웠던 적이 있다.)

    for(int i = 1; i <= n; i++)
    {
        int count = 0;
        for(int j = 1; j <= n; j++)
            if (graph[i][j] == true || graph[j][i] == true)
                count++;
        if (count == n - 1)
            answer++;
    }

내가 확실히 승리할 수 있는 선수의 수와 내가 붙으면 확실히 지는 선수의 수를 합한 값이 n - 1 이라면 모두와의 비교가 가능하다는 뜻이니 나는 순위를 확실히 정할 수 있는 사람이므로 이때 answer를 1 증가시킨다. graph[i][j], graph[j][i] 둘 중 하나라도 True 값이라면 동일한 경기에서 누구는 지고 누구는 이겼다는 뜻이니 비교 가능한 경우다.

👱‍♀️ 최단 경로 찾는 알고리즘 비교 (BFS, 다익스트라, 벨만포드, 플로이드 와샬)

BFS	다익스트라	벨만포드	플로이드 와샬
가중치가 있는 그래프 ❌불가능 가중치가 모두 동일하거나 없어야 한다. 이건 DFS도 마찬가지!	가중치가 모두 다른 그래프 ⭕가능	가중치가 모두 다른 그래프 ⭕가능	가중치가 모두 다른 그래프 ⭕가능
가중치 없고 모두 동일한 중요도를 가져야 함	가중치가 양의 정수일 때만 가능하다.	가중치가 음의 정수일 때도 가능하다.	가중치가 음의 정수일 때도 가능하다.(단, 음의 사이클이 없어야 한다.)
큐 사용	우선순위 큐 사용	Dynamic Programming 방식 distance[n] = min(distance[n], distance[m] + E(m, n))	Dynamic Programming 방식 distance[i,j] = min(distance[i,j], distance[i,n] + distance[n,j]) 이차원 배열(행렬) 사용
O(E)	우선순위 큐를 사용할 경우 O(ElogV) 플로이드 처럼 모든 정점-모든 정점 최단 경로를 구할 경우 O(V * ElogV)	O(VE)	3중 for문을 사용하므로 O(V^3)
하나의 특정 정점에서 다른 정점들까지의 최단 경로를 구함 1:N	하나의 특정 정점에서 다른 정점들까지의 최단 경로를 구함 1:N	하나의 특정 정점에서 다른 정점들까지의 최단 경로를 구함 1:N	모든 정점들간의 쌍에 대해 최단 경로를 한번에 구함 즉 모든 정점들간의 최단 경로를 모두 구한다.N:M

• 다익스트라 시간복잡도 설명
  • 👉 O(VlogV + ElogV) = O((V + E)logV) = O(ElogV)
  • V * logV
    • 모든 정점마다 한번씩 방문하게 됨 V
    • 루트를 pop 하고 다시 힙정렬하는 과정이 logV
  • E * logV
    • 이웃 정점을 예약하는건 곧 간선을 검사하는 것과 같다. E
    • 이웃 정점 push 하고 다시 힙정렬하는 과정이 logV

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Algorithm 카테고리 내 다른 글 보러가기