위키피디아에 있는 코드¹이 왠지 어려워서 나름대로 주석을 좀 추가하고 정리를 해봤는데, 그래도 어렵다. 그림을 그려서 설명하면 그나마 좀 괜찮은데 글로만 설명하려니 역시 쉽지 않은듯.

알고리즘 설명

시작노드를 설정 후 모든 노드에 대해(메인 루프) 아래 2가지 루프를 적용한다.

• 서브 루프1: 현재 노드에서 도달 가능한 모든 노드 중 최소거리인 노드를 찾은 후 현재노드값을 해당 위치로 변경

• 서브 루프2: 변경된 현재 노드까지 오는 최단거리를 알고있으므로, 이 값을 기준으로 다른 모든 노드들에 도달하는 거리를 한번씩의 덧셈으로 업데이트 한다. (현재노드까지 최단거리값 + 현재노드에서 다음노드 거리 = 출발노드에서 다음 노드까지의 최단거리)

  typedef 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; } // 시작점 설정, 시작점에서 시작점까지의 거리는 0 d[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) }

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

  typedef 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;       }         // 시작점 설정, 시작점에서 시작점까지의 거리는 0       d[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)   }