개념 - 최단 경로 알고리즘 (Dijkstra, Floyd)

이전 쓰레드에서는 최단 신장 트리를 찾는 알고리즘으로 Kruskal과 Prim의 알고리즘을 공부했다. 

복습할 겸 생각해보면 Kruskal은 사이클을 이루지 않는 가장 빠른 '경로'를 하나씩 추가해 나가는 것이다. 경로 수가 e일 때, 힙을 사용하여 최단경로를 정렬하기에 e개의 최적 경로 하나를 도출할 때 log e의 시간이니 O(e log e)가 소요된다.

Prim은 갈 수 있는 정점 중 제일 가까운 정점을 하나 씩 추가해 나간다. 좀 더 구현적으로 살펴보면 딱 정점 수 만큼 루프를 돌면서 루프 한 단계를 돌 때마다 또 정점 수 만큼의 루프를 돌아서 가장 까가운 점들의 정보를 갱신한다.  n개의 정점 하나마다 n개의 점과의 거리를 갱신 해야하니 O(n^2) 

이제 최단 경로 알고리즘을 살펴보자.

Dijkstra 알고리즘

다익스트라 알고리즘은 n개의 정점이 있다고 할 때 처음 들어온 정점의 인접 정점 정보부터 해서 가장 가까운 새 정점을 찾아가면서 정점 정보를 갱신해나가는 형식이다. 여기까진 prim 알고리즘이랑 설명이 똑같지않은가? 그러나 prim은 새로 추가한 정점과 남은 정점들과의 거리가 기존보다 가까우면 바로 정보를 갱신하는 반면, dijkstra는 처음에 들어온 정점으로부터의 최단거리를 계속해서 유지한다. 

예를들어 만약 A에서 C로 가는 비용이 20인데 A에서 B로 가는 비용 15, B에서 C로 가는 비용 15라면

prim의 경우 먼저 B로가서 B->C의 거리 15를 기록해두겠지만, dijkstra의 경우 B로 가고나서 A->C의 비용 20과 A->B->C의 비용 30을 비교한 후 더 저렴한 A->C의 비용 20를 그냥 남겨둔다. prim과 마찬가지로 모든 정점을 순회하지만 기록에는 A(시작점)로부터 모든 점까지의 최단거리들만 남게될 것이다.

prim과 마찬가지로 N개의 정점을 순회하면서 N개의 정점과의 관계를 갱신하므로 O(n^2). (단, 인접배열 대신 인접리스트를 사용하고 최단점 갱신에 힙을 사용하면 O(ElogV) 까지는 갈 수 있다...고 인터넷에서 봤다.)

Floyd 알고리즘

뭔가 설명을 잘 읽고 이해하지 못하면 혼자서 이해하기가 힘들다. 특히 책의 설명은 수식이 곁들여져있어서 이해하지 못하다가 인터넷으로 이해하고 나니 그제서야 이게 그뜻이구나 하고 이해가 되었다. 위키에는 동적 뭐시기 접근법이라고 한다나.. 나중에 배우겠지만 어쨌든

플로이드 알고리즘은 이중배열 하나와 삼중 포문으로 작동한다. n개의 정점이 있을 때 i, j의 범위는 [0 : n) 으로 dist[i][j]는 n개의 정점간의 모든 비용을 표현할 것이다. 안쪽 포문 두개는 그냥 직관적으로 이해할 수 있다.

그런데 제일 바깥에 k 포문이 하나 더 있다. 이 녀석은 뭘까? 가장 바깥에 있으므로 k가 1 증가할 때마다 이중 포문이 한번 도므로 모든 거리가 갱신된다는 걸 알 수있다. 

    for (int k = 0; k < size; ++k)
        for (int j = 0; j < size; ++j)
            for (in i = 0; i < size; ++i)
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];

dist[i][j]의 의미는 i로부터 j 까지의 거리라는 의미이고, dist[i][k]는 i부터 k까지의 거리, dist[k][j]는 k부터 j까지의 거리다. 따라서 

0부터 size -1까지의 모든 정점 k에 대해서 i에서 j로 가는 현재 알려진 최단거리^[각주:1]보다 i에서 k를 경유해서 j로 가는 거리가 짧다면 dist[i][j]를 그 경유한 거리로 갱신하는 것이다. 따라서 모든 k가 종료된 후에는 더이상 짧은 거리가 남아있을 수가 없다. O(n^3).

1. k-1까지 알려진 거리 [본문으로]