디익스트라 알고리즘(Dijkstra algorithm)

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

알고리즘 설명

시작노드를 설정 후 모든 노드에 대해(메인 루프) 아래 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. 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