Floyd-Warshall. Bellman-Ford. Dijkstra 알고리즘

뭐... 세 알고리즘 모두 최단 경로를 찾는 데 사용되는 알고리즘입니다.

그래프 관련해서 상당히 유용한 알고리즘이기도 하고 실제로도 쓸 일이 굉장히 많은 알고리즘입니다. (아마)

편의상 말은 짧게 하겠습니다.

어느 온라인 저지를 가도 비슷한 문제가 몇개씩 있겠지만.. 나한텐 가장 익숙한 koistudy.net을 두고 설명하겠다.

문제는 뭐.. 1번 정점에서 n번 정점을 가는데 걸리는 최소 거리를 출력하는 거다.

R&E가는길 (Tiny) (n<10. 간선 < 30)

R&E가는길 (Small) (n<500. 간선 < 4000)

R&E가는길 (Large) (n<10000. 간선 < 100000)

보통 이러한 입력의 데이터는 인접행렬을 잡아서 푼다. (사실 std::vector를 이용해 인접 리스트 형식으로 저장하는 게 훨씬 좋지만, 배우고 나서 그렇게 풀자.)

n^2짜리 판(배열)을 잡은다음에.. adj[i][j] = i~j까지의 거리라고 가정하고 푸는 것이다.

일방통행.. 그런 얘기는 없으니 adj[i][j] = adj[j][i]이다. 

또한. 경로가 없는 경우에는 adj[i][j]  = 무한으로 잡자. (진짜 무한을 쓰진 않고 엄청 큰 수를 넣는다. 문제에서 경로가 길어봐야 1000이니까 1억만 넘어도 거의 무한이라 칠 수 있다.)

1. Floyd-Warshall

짱 쉽다.

달리 설명할 필요가 없음..

이런 게 있는 줄 모르고 Dijkstra를 먼저 찾아보고 좌절하던 나의 모습이 떠오른다.

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

#include <cstdio> int adj[15][15],n;   int floyd(){     for(int i=1; i<=n; i++){         for(int j=1; j<=n; j++){             for(int k=1; k<=n; k++){                 if(adj[j][k] > adj[j][i] + adj[i][k]){                     adj[j][k] = adj[j][i] + adj[i][k];                 }             }         }     }     return adj[1][n]; }

설명하자면..
그냥 루프를 계속 돌려서. (j - k로 가는 경로 > j - k로 i를 경유해서 가는 경로) 일때 경로를 갱신해준다.

모든 쌍에 대해서 저렇게 갱신해 준다. (그래서, adj[1][n]이 아니라 adj[3][5]를 불러와도 얜 최단경로이다.)

루프 순서에 주의해 주자! 경유지 / 시작점 / 끝점 순으로 돌린다.

시간 복잡도는 딱 보면 알수 있겠지만.. 이다.

이 소스로 문제를 풀어보면 Tiny 0ms. Small 138ms. Large TLE가 뜬다.

쉽긴 쉽지만, 조금 더 빠른 방법이 필요함을 알 수 있다.

2. Bellman-Ford Algorithm

사실 이 글을 쓴 이유다.

네트워크 플로우 관련해서 책 뒤지다 보니까 벨만 포드 알고리즘이 나오는데 도대체 저게 뭔 소리인지 몰라서 ㅡㅡ 별 자료를 다 찾아봤는데

사실 쉬운 알고리즘이더라.. 어쨌든. 시작해보자.

이제부터는 모든 쌍에 대한 최단경로는 안나오고. 시작점(1번 점)에서의 최단경로만 알 수 있다.

그리고.. 문제에서는 딱히 요구하지는 않는데. 경로 추적을 해보자. 네비게이션을 켰는데 목적지까지의 최단경로 길이만 나오고 최단경로가 안나오면 얼마나 당황스럽겠는가 (...) 쓸일이 많으니 배워두는 게 좋다.

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

#include <cstdio> #include <cstring> int shortest[505], parent[505]; int n,adj[505][505];   void bellmanFord(){     memset(shortest,0,sizeof(shortest));     memset(parent,0,sizeof(parent));     shortest[1] = 0;     bool update = 1;     while (update){         update = 0;         for (int j=1; j<=n; j++) {             for (int k=1; k<=n; k++) {                 if(shortest[k] > shortest[j] + adj[j][k]){                     shortest[k] = shortest[j] + adj[j][k];                     parent[k] = j;                     update = 1;                 }             }         }     } }

shortest와 parent라는 새로운 배열이 눈에 띈다.

shortest는 시작 점에서의 최단 경로를 저장하고. parent는 이 점을 거치기 바로 전에 지나는 점을 뜻한다.

즉. 경로가 1 -> 4 -> 5 -> 8 이라 하면 parent[8] = 5. parent[5] = 4... 이렇게.

 

초기에 최단 경로가 어느정돈지 모르니까 일단 무한으로 잡고 (memset 어쩌구가 있는데.. 약간의 트릭을 써서 대략 10억 언저리의 값으로 배열을 초기화한 것이다. memset에 관해 모르면 한번 찾아보길)

또한 parent에 대해서도 아는 게 하나도 없으니까 비워둔다. (전역변수면 상관없겠지만)

다만. 시작점에서 시작점으로의 최단 거리는 0이니까. shortest[1] = 0으로 잡자.

... 사실 아까 그점만 알면 딱히 플로이드랑 다른 점은 없다.

아니. 똑같다. shortest[x] = adj[1][x]라고 생각해보자. 한 점을 중심으로 계속 빙빙 돌린다는 것 말고 차이가 없다. 대신 한번으로는 모자랐는지, 변경사항이 있을 때까지 계속 돌린다는 게 차이점일 것이다. (update 변수를 잘 주목하라)

경로 추적은... 1 - k를 1 - j - k로 바꿨으니. parent[k] = j일 것이다. 

시간 복잡도는 이라고 한다.

n^3일줄 알았는데 update가 그만큼 돌아가지는 않는 듯 하다.

Tiny 0ms. Small 0ms. Large TLE.

개선이 있었다.

3. Dijkstra Algorithm

웬만하면 BFS를 깨우치고 배우길 권한다. 멋진 블로그가 있다.

다익스트라 알고리즘의 기본 틀은 이렇다.

while(1){

1. 시작 점에서 가장 가까우면서, 방문하지 않은 점 검색. (점을 i라 둠)

2. 그 점을 방문.

3. 방문하지 않은 점들이. 그 점을 거쳐가면 빠른지 확인. (shortest[j] > shortest[i] + adj[i][j])

3-1. 만약 빠르면. 최단 경로와 함께 parents 역시 갱신.

}

이 애니메이션을 멍하니 보면 이해가 갈 거다.

상당히 BFS와 유사한 방법을 사용해서 갱신을 하고 있다.

한 점이 연결되어 있는 점은 최대 n개이고. 검색하는데 드는 시간도 n인데. 점을 많아야 n번 방문하니. n*(n+n) = 이다.

Large를 노릴 만 하다.

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

#include <cstdio> #include <cstring>   int shortest[505],parent[505],visited[505]; int adj[505][505],n,min,via;   void dijkstra(){     while (1) {         min = 1e9; // 10억         for (int i=1; i<=n; i++) {             if(!visited[i] && min > shortest[i]){                 min = shortest[i];                 via = i;             }         }         visited[via] = 1;         for (int i=1; i<=n; i++) {             if(!visited[i] && shortest[i] > adj[via][i] + shortest[via]){                 shortest[i] = adj[via][i] + shortest[via];                 parent[i] = via;             }         }     } }

소스 코드는.. 딱히 어렵지 않다. 역시 Small까지 0ms다.

하지만, 배열 사이즈를 적절히 조절해서 Large에 내면 아마 Runtime Error / Time Limit Exceeded 둘 중 하나가 뜰거다.

왜냐... 기본적으로 자료 구조의 낭비가 너무 심하기 때문이다.

Large 문제에서 간선은 100000개니까. 양방향으로 200000개라 쳐도,

인접행렬은 1억개의 int 값을 쳐묵쳐묵한다. 메모리 400MB이다. 애초에 그게 문제인 것이다.

조금 더 빠르고 효율적인 자료구조가 필요하다.. 그런데 STL에는 vector라는 짱짱 좋은 자료구조가 있다.

여기서 vector의 사용법을 배우면, 대략 vector를 이런 식으로 그래프에 맞게 적용시킬수가 있다.

다만. 저 글에서는 std::pair를 썼는데, 그냥 난 구조체를 하나 잡아서 쓰려고 한다.

struct edge{int pos,dist;};

이렇게 edge라는 구조체를 잡겠다.

뭐 이제 어쩌라고... 조금 막막해지는데, 

어차피 visited하고 shortest는 그대로다. 갱신하는 부분만 바꾸면 된다.

adj[via][i]가 포인트다. 종전에는 이걸 1~n까지 무식하게 다 찾아봤는데, 이제 그럴 거 없고 via에 연결된 놈만 보면 된다.

Colored By Color Scripter™

1 2 3 4 5 6 7 8

std::vector<edge> graph[10001];   for(int i=0; i<graph[via].size(); i++){     edge t = graph[via][i];     if(shortest[t.pos] > shortest[via] + t.dist){         shortest[t.pos] = shortest[via] + t.dist;     } }

대강 이렇게..

이러면 Large가 400ms대에서 Accept된다.

(Bellman - Ford도 이렇게 하는 방법이 있다. 찾아보길)

4. Heap을 사용한 Dijkstra Algorithm

여기서 조금 더 나아갈 수 있다.

처음으로 돌아가서. 다익스트라의 기본 꼴을 보자.

while(1){

1. 시작 점에서 가장 가까우면서, 방문하지 않은 점 검색. (점을 i라 둠)

2. 그 점을 방문.

3. 방문하지 않은 점들이. 그 점을 거쳐가면 빠른지 확인. (shortest[j] > shortest[i] + adj[i][j])

3-1. 만약 빠르면. 최단 경로와 함께 parents 역시 갱신.

}

그런데, 방문하지 않은 점을 조금 더 빠르게 검색할 수 있다.

힙을 쓰면 된다. 힙을 쓰면 가장 가까운 점 (최소값) 이 lgn 시간에 나온다. 짱짱 빠르다

std::priority_queue<edge> shortest로 shortest를 힙으로 바꿔주자.

(그냥 해서는 안된다. edge의 비교연산을 정의해야 하는데 연산자 오버로딩을 구글링해보길 권한다. 어렵지 않다. 참고로 priority_queue는 큰 값 먼저 나오니까 적절한 오버로딩으로 작은 값 먼저 나오게 하자)

그러면 1번 과정을 그냥 shortest.pop()으로 한 줄에 할 수 있다.

문제는.. 그 점을 거쳐가면 빠른지를 확인해야 하는데,

저게 힘들다.

힘드니까 그냥 생각하지 말자.

3번 루틴을 바꾼다.

while(1){

1. 시작 점에서 가장 가까우면서, 방문하지 않은 점 검색. (점을 i라 둠)

2. 그 점을 방문.

3. 방문하지 않은 점들이. 그 점을 거쳐가면 빠른지 확인. 그냥 방문하지 않기만 하면 shortest에 때려박는다.

}

????

이래도 된다.

왜냐? 결국 한 정점은 한번만 거쳐가니까. 결국 힙에서 꺼낼 때는 가장 작은 놈 하나가 나올 거고. 3번 과정에서 큰 놈들을 아무리 때려박더라도 힙은 작은 놈 하나만 보고 나머지는 다 무시한다. (물론 그냥 무시하지는 않는다. visited[i] 배열을 통해 무시하도록 코딩을 하자)

parent[i] 배열 쓰는건 변함이 없다.

결론은 이거다.

while(1){

1. priority queue에서 방문하지 않은 가장 작은 점을 pop

2. 그 점을 방문.

3. 그 점과 연결된 점을 모조리 priority queue에 push

}

소스 코드는 생략한다..

이로써 다익스트라 알고리즘이 얼마나 bfs에 기반해 있는지가 아주 노골적으로 드러나게 된다.

(저 소스를 처음 짰을때 내가 뭔가 잘못해서 bfs 비슷한 코드가 나온 줄 알았다 ㅡㅡ;)

시간 복잡도를.. 생각해보자.

일단 힙에 들어있는 요소의 양이 최대 M일 텐데. O(logM) < O(logN^2) = O(logN)니까 이건 O(lgN). 이걸 N번.

큐에 각 정점들을 한번씩은 push하니까 M * logN

복잡도는 이다.

(굳이 왜 logm 말고 logn이라 그랬냐면.. 위키백과에서 그렇게 써서 그렇게 쓴거다 (...))

Large 70ms Accepted.

가장 빠른 방법은 아니고. 피보나치 힙 등... 더 빠른 방법이 있지만 그 중 내가 아는 건 하나도 없기 때문에 이 방법으로 썼다.

참고로. 다익스트라는 거리가 음수이면 처리를 안하니 그럴 때는 벨만 포드 알고리즘을 쓰자.

생각보다 글이 더럽게 길었는데..

어쨌든 최단 경로 구하는 알고리즘은 이것저것 쓸데가 많으니 꼭 익혀두도록 하자.

(그리고 웬만하면 인접행렬 쓰지 말고 그래프로...)