위키피디아에 있는 코드1이 왠지 어려워서 나름대로 주석을 좀 추가하고 정리를 해봤는데, 그래도 어렵다. 그림을 그려서 설명하면 그나마 좀 괜찮은데 글로만 설명하려니 역시 쉽지 않은듯.
알고리즘 설명
시작노드를 설정 후 모든 노드에 대해(메인 루프) 아래 2가지 루프를 적용한다.
- 서브 루프1: 현재 노드에서 도달 가능한 모든 노드 중 최소거리인 노드를 찾은 후 현재노드값을 해당 위치로 변경
-
서브 루프2: 변경된 현재 노드까지 오는 최단거리를 알고있으므로, 이 값을 기준으로 다른 모든 노드들에 도달하는 거리를 한번씩의 덧셈으로 업데이트 한다. (현재노드까지 최단거리값 + 현재노드에서 다음노드 거리 = 출발노드에서 다음 노드까지의 최단거리)
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849typedef int weight;const weight infinity = INT_MAX;const int undefined = -1;// n은 노드의 갯수,// w는 노드간 가중치를 나태낸 [n x n] adjacent matrix, 즉 w[i][j] 위치에 노드i, 노드j 간의 가중치가 저장되어있음// s는 시작 노드 번호// d는 시작점으로부터 각 노드까지의 거리(함수가 종료되고난 후 최단거리 결과값을 얻을 수 있음)void dijkstra(int n, const int w[][n], int s, weight d[]){bool is_in_S[n]; // 노드 방문 여부 표시// 초기화for (int v = 0; v < n; ++ v){d[v] = infinity;is_in_S[v] = false;}// 시작점 설정, 시작점에서 시작점까지의 거리는 0d[s] = 0;// 복잡도:(n회 루프)for (;;) {weight min = infinity;int u = undefined;// 복잡도:(n회 루프)// 도달가능한 노드중에 방문을 하지 않았으면서 최소거리인 노드를 찾고, 해당 위치를 u 로 설정한다.for (int v = 0; v < n; ++ v)if (!is_in_S[v] && min > d[v])min = d[v], u = v;if (u == undefined) // 추가로 도달할 수 있는 점이 없다.break;// u값이 존재할 경우 u노드를 방문한 것임.// 해당 노드에 방문했다고 표기.is_in_S[u] = true;// 복잡도:(n회 루프)for (int v = 0; v < n; ++ v)if (w[u][v] != infinity && d[v] > d[u] + w[u][v])d[v] = d[u] + w[u][v];}// 알고리즘 복잡도: n회 x (n회 + n회) = O(n^2)}
-
http://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98↩