Dijkstra Algorithm (다익스트라 알고리즘)

• 하나의 시작 정점에서 다른 정점까지의 최단 경로를 구할 때 이용하는 알고리즘
• 단일점에서의 최단 경로 알고리즘 (One to All Shortest Path) 중 가장 많이 사용
• 무방향 그래프나 방향 그래프에 모두 적용 가능
• Dynamic Programming으로 풀 수 있음

Weight Adjacent Matrix (가중치 인접 행렬)

• 가중치 인접 행렬 : 그래프의 가중치를 표현한 행렬
• 최단 경로를 구하려는 그래프를 가중치 인접 행렬을 이용해서 표현할 수 있음
• 그래프에서 사용하는 인접 행렬과 같은 형태의 2차원 배열
• 두 정점 사이에 간선이 없으면 무한대 값을 저장
• 각 정점은 자기 자신과 이어진 간선을 허용하지 않으므로 가중치 인접 행렬에서 대각선 값은 0

다익스트라 최단 경로 알고리즘에서 최단 경로 찾기

1. 경로 길이를 저장할 배열 distance 준비
   • 시작 정점으로부터 각 정점에 이르는 경로의 길이를 저장하기 위한 배열 distance를 $\infin$로 초기화
2. 시작 정점 초기화
   • 시작 정점의 distance를 0으로 초기화하고 집합 S에 추가
3. 최단 거리 수정
   1. 집합 S에 속하지 않은 정점 중에서 distance가 최소인 정점 u를 찾아 집합 S에 추가
   2. 새로운 정점 u가 추가되면, u에 인접하고 집합 S에 포함되지 않은 정점 w의 distance값을 다음 식에 따라 수정
      • distance[w] ← min(distance[w], distance[u] + weight[u][w])
   3. 집합 S에 모든 정점이 추가될 때까지 3을 반복한다.

다익스트라 알고리즘 - 인접 행렬 이용

• C++로 구현

  #include <stdio.h>
  #include <algorithm>
  using namespace std;
  
  #define INF 10000000
  #define N 5
  
  int weight[N][N] = {{0, 10, 5, INF, INF},
                      {INF, 0, 2, 1, INF},
                      {INF, 3, 0, 9, 2},
                      {INF, INF, INF, 0, 4},
                      {7, INF, INF, 6, 0}};
  bool visited[N] = {false};
  int dist[N] = {0};
  int min_node = 0;
  
  // 방문하지 않은 노드들 중,
  // 최단 거리가 가장 짧은 노드 인덱스 반환
  int get_smallest_node()
  {
      int min = INF;
      int node = -1;
      for (int i = 0; i < N; i++)
      {
          if (visited[i] == true)
              continue;
          if (min > dist[i])
          {
              min = dist[i];
              node = i;
          }
      }
      return node;
  }
  
  void dijkstra(int start)
  {
      // 방문한 노드에 시작 정점 저장
      visited[start] = true;
      // distance 배열 초기화
      for (int i = 0; i < N; i++)
      {
          dist[i] = weight[start][i];
      }
  
      while (1)
      {
          // 1. 최소 노드 추가
          min_node = get_smallest_node();
          if (min_node == -1)
          {
              break;
          }
          visited[min_node] = true;
  
          // 2. 1로 인해 단축되는 경로 있는지 확인하여 distance 값 수정
          for (int i = 0; i < N; i++)
          {
              if (visited[i] == true || weight[min_node][i] == INF)
              {
                  continue;
              }
              dist[i] = min(dist[i], dist[min_node] + weight[min_node][i]);
          }
      }
  }
  
  int main(void)
  {
      dijkstra(0);
      for (int i = 0; i < N; i++)
          printf("dist[%d]: %d\n", i, dist[i]);
  
      return 0;
  }

다익스트라 알고리즘 - Heap 자료구조 이용

• 위의 방법은 정점 개수만큼 for문을 두 번 써서 순회 → 시간복잡도 $O(V^2)$

• 우선순위 큐(=힙)을 써서 최단거리가 가장 짧은 노드를 탐색할 경우 → 최악의 경우 시간 복잡도 $O((E+V)\log V)$

• C++로 구현

  #include <stdio.h>
  #include <algorithm>
  #include <vector>
  #include <queue>
  using namespace std;
  
  #define INF 10000000
  #define N 5
  
  // graph[0].first = 정점 0에서 first로 감
  // graph[0].second = 정점 0에서 first로 갈 때 드는 비용
  vector<pair<int,int>> graph[N];
  // 최단거리 배열
  int shortest_distance[N];
  
  void dijkstra(int start)
  {
      int distance = 0, min_node_index = 0, new_cost = 0;
      priority_queue<pair<int,int>> pq; // {거리, 정점 인덱스}, 우선순위 큐는 기본이 내림차순임에 유의
  
      pq.push({0, start}); // 시작 정점으로 가기 위한 최단 경로는 0으로 설정
      shortest_distance[start] = 0;
  
      while (!pq.empty())
      {
          // 최단 거리 노드(min_node_index) 찾기
          min_node_index = pq.top().second;
          distance = -pq.top().first;
          pq.pop();
  
          if (shortest_distance[min_node_index] < distance) // 이미 최단경로를 체크한 경우
              continue;
  
          for (int i = 0; i < graph[min_node_index].size(); i++)
          {
              int modifying_node = graph[min_node_index][i].first;
              int second_cost = graph[min_node_index][i].second;
  
              new_cost = distance + second_cost;
              if (new_cost < shortest_distance[modifying_node])
              {
                  shortest_distance[modifying_node] = new_cost;
                  pq.push({-new_cost, modifying_node});
              }
          }
      }
  }
  
  int main(void)
  {
    // 간선 정보 입력.
    // 아래 줄 내용: 정점 0에서 정점 0으로 갈 때 드는 비용은 0이다
    graph[0].push_back({0, 0});
    graph[0].push_back({1, 10});
    graph[0].push_back({2, 5});
  
    graph[1].push_back({1, 0});
    graph[1].push_back({2, 2});
    graph[1].push_back({3, 1});
  
    graph[2].push_back({1, 3});
    graph[2].push_back({2, 0});
    graph[2].push_back({3, 9});
    graph[2].push_back({4, 2});
  
    graph[3].push_back({3, 0});
    graph[3].push_back({4, 4});
  
    graph[4].push_back({0, 7});
    graph[4].push_back({3, 6});
    graph[4].push_back({4, 0});
  
    // 최단거리 배열을 모두 INF로 초기화
    fill(shortest_distance, shortest_distance + N, INF);
  
    dijkstra(0);
  
    for (int i = 0; i < N; i++)
    {
        printf("shortest_distance[%d]: %d\n", i, shortest_distance[i]);
    }
    return 0;
  }