Dijkstra

CHOYEAH·2023년 11월 1일
알고리즘
0
post-custom-banner

최단경로 알고리즘 - 다익스트라

개념

최단 경로 알고리즘 다익스트라는 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알 수 있습니다. 즉 가중치 그래프 (Weighted Graph) 에서 간선 (Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적이라고 볼 수 있습니다. 이러한 알고리즘은 많은 실생활 문제를 모델링 할 수 있으며, 인공위성 GPS 소프트웨어 등에서 가장 많이 사용되며 네트워크 라우팅, 맵에서의 경로 탐색, 데이터 네트워크에서 패킷 전송 등 다양한 분야에서 사용됩니다.

다만 그래프에 음의 간선이 있는 경우는 사용이 불가합니다. 현실세계에는 음의 간선이 존재하지 않기 때문에 다익스트라는 현실 세계에 사용하기 매우 적합한 알고리즘 중 하나라고 할 수 있습니다.

다익스트라는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있기 때문에 다이나믹 프로그래밍으로 분류되기도 합니다. 또한 정렬을 사용하기 때문에 정렬 이후에 가장 적은 가중치를 선택하게되는데 그런 이유로 그리디 알고리즘으로도 분류되기도 합니다.

최단 경로 문제 종류

  1. 단일 출발 및 단일 도착 (single-source and single-destination shortest path problem) 최단 경로 문제
    • 그래프 내의 특정 노드 u 에서 출발, 또다른 특정 노드 v 에 도착하는 가장 짧은 경로를 찾는 문제
  2. 단일 출발 (single-source shortest path problem) 최단 경로 문제
    • 다익스트라, 벨만포드 알고리즘 등의 최단경로 알고리즘이 있음
      • 상세 다익스트라 알고리즘과 벨만-포드 알고리즘은 둘 다 최단 경로를 찾는 알고리즘입니다. 이 둘은 각기 다른 특징과 제약사항이 있습니다.

        1. 다익스트라 알고리즘: 주로 양의 가중치를 가진 그래프에서 사용됩니다. 시작 노드에서 그래프의 모든 노드까지의 최단 거리를 찾는데 효과적입니다. 하지만 음의 가중치가 있는 그래프에서는 사용할 수 없습니다.

        2. 벨만-포드 알고리즘: 음의 가중치를 가진 그래프에서도 사용할 수 있습니다. 또한, 이 알고리즘은 음의 사이클을 감지할 수 있습니다. 그러나 다익스트라 알고리즘보다 비효율적인 경우가 많습니다.

          이 외에도 여러 최단 경로 알고리즘이 있습니다. 대표적인 예로는 플로이드-워셜 알고리즘과 A* (A-star) 알고리즘이 있습니다.

        3. 플로이드-워셜 알고리즘: 모든 노드 쌍 간의 최단 경로를 찾습니다. 즉, 이 알고리즘은 그래프의 모든 노드에서 모든 다른 노드로 가는 최단 경로를 찾습니다. 이는 "모든 쌍 최단 경로" 문제를 해결하는 데 사용됩니다. 이 알고리즘은 음의 가중치를 가진 간선이 있어도 사용할 수 있지만, 음의 가중치를 가진 사이클은 없어야 합니다.

        4. A (A-star) 알고리즘: 휴리스틱을 사용하여 경로를 찾는 알고리즘입니다. 이는 특정 목표까지의 경로를 추정하여 효율적으로 경로를 찾습니다. 이 알고리즘은 주로 경로 찾기 문제에 사용되며, 예를 들어 게임에서 가장 빠른 경로를 찾는 데 사용됩니다. A* 알고리즘은 시작 노드에서 목표 노드까지의 최단 경로를 찾는 데 효과적입니다.

    • 그래프 내의 특정 노드 u 와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제

      예를 들어 A, B, C, D 라는 노드를 가진 그래프에서 특정 노드를 A 라고 한다면, A 외 모든 노드인 B, C, D 각 노드와 A 간에 (즉, A - B, A - C, A - D) 각각 가장 짧은 경로를 찾는 문제를 의미함

  3. 전체 쌍(all-pair) 최단 경로 문제
    • 그래프 내의 모든 노드 쌍 (u, v) 에 대한 최단 경로를 찾는 문제

장점

  1. 최단 경로를 찾을 수 있다는 점은 가장 큰 장점입니다.
  2. 이 알고리즘은 효율적이며, 대부분의 그래프에 적용할 수 있습니다.
  3. 다양한 분야에서 사용될 수 있으며, 실제 문제에 대한 해결책을 제공합니다.

단점

  1. 가중치가 음수인 경우, 일부 최단 경로 알고리즘이 잘 작동하지 않을 수 있습니다.
  2. 복잡한 그래프에서 시간 복잡도가 높을 수 있습니다.
  3. 모든 노드 간의 최단 경로를 찾는 경우, 결과를 저장하기 위해 많은 메모리를 필요로 할 수 있습니다.

사용에 적합한 상황

최단 경로 알고리즘은 특히 그래프 데이터 구조를 사용해야 하는 문제를 해결하는 데 적합합니다. 예를 들어, 위치 간의 최단 거리 또는 최소 비용을 찾아야 하는 네트워크 라우팅, 맵에서의 경로 탐색, 데이터 네트워크에서의 패킷 전송 등의 문제를 해결하는 데 사용됩니다.

사용에 부적합한 상황

  1. 그래프에 음의 가중치가 있는 경우, 일부 알고리즘 (예 : 다익스트라)은 잘 작동하지 않을 수 있습니다.
  2. 그래프가 너무 크거나 복잡한 경우, 최단 경로 알고리즘은 시간과 공간의 복잡성 때문에 부적합할 수 있습니다.

주의사항

음의 사이클이 존재하는 그래프에서는 최단 경로를 찾을 수 없습니다. 이는 음의 사이클을 계속 따라가면서 경로의 총 비용을 무한히 줄일 수 있기 때문입니다.

시간복잡도

일반적으로, 다익스트라 알고리즘의 시간 복잡도는 O(E+VlogV)입니다. 여기서 E는 에지의 수, V는 노드(vertex)의 수입니다. (벨만-포드 알고리즘의 경우, 시간 복잡도는 O(VE))

  • 다익스트라 알고리즘은 크게 다음 두 가지 과정을 거침
    • 과정1: 각 노드마다 인접한 간선들을 모두 검사하는 과정
    • 과정2: 우선순위 큐에 노드/거리 정보를 넣고 삭제(pop)하는 과정
  • 각 과정별 시간 복잡도
    • 과정1: 각 노드는 최대 한 번씩 방문하므로 그래프의 모든 간선은 최대 한 번씩 검사. 즉, 각 노드마다 인접한 간선들을 모두 검사하는 과정은 O(E)
    • 과정2: 우선순위 큐에 가장 많은 노드, 거리 정보가 들어가는 경우, 우선순위 큐에 노드/거리 정보를 넣고, 삭제하는 과정이 최악의 시간이 걸림
      • 우선순위 큐에 가장 많은 노드, 거리 정보가 들어가는 시나리오는 그래프의 모든 간선이 검사될 때마다, 배열의 최단 거리가 갱신되고, 우선순위 큐에 노드/거리가 추가되는 것임
      • 이 때 추가는 각 간선마다 최대 한 번 일어날 수 있으므로, 최대 O(E)의 시간이 걸리고, O(E) 개의 노드/거리 정보에 대해 우선순위 큐를 유지하는 작업은  가 걸림 𝑂(𝑙𝑜𝑔𝐸)
  • 총 시간복잡도:
    • 과정1 + 과정2 = O(E) + O(ElogE) = O(E + ElogE) = O(ElogE)
      • O(E)는 생략됨
      • E는 간선(엣지)

알고리즘 로직

  • 첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며, 최단 거리를 갱신하는 기법
  • 다익스트라 알고리즘은 너비우선탐색(BFS)와 유사
    • 첫 정점부터 각 노드간의 거리를 저장하는 배열을 만든 후, 첫 정점의 인접 노드 간의 거리부터 먼저 계산하면서, 첫 정점부터 해당 노드간의 가장 짧은 거리를 해당 배열에 업데이트

      다익스트라 알고리즘의 다양한 변형 로직이 있지만, 우선순위 큐를 사용하는 방식을 기준으로 설명

  • 우선순위 큐를 활용한 다익스트라 알고리즘
    • 우선순위 큐는 MinHeap 방식을 활용해서, 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼내게 됨
    1. 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장
      • 초기에는 첫 정점의 거리는 0, 나머지는 무한대로 저장함 (inf 라고 표현함)
      • 우선순위 큐에 (첫 정점, 거리 0) 만 먼저 넣음
    2. 우선순위 큐에서 노드를 꺼냄
      • 처음에는 첫 정점만 저장되어 있으므로, 첫 정점이 꺼내짐
      • 첫 정점에 인접한 노드들 각각에 대해, 첫 정점에서 각 노드로 가는 거리와 현재 배열에 저장되어 있는 첫 정점에서 각 정점까지의 거리를 비교한다.
      • 배열에 저장되어 있는 거리보다, 첫 정점에서 해당 노드로 가는 거리가 더 짧을 경우, 배열에 해당 노드의 거리를 업데이트한다.
      • 배열에 해당 노드의 거리가 업데이트된 경우, 우선순위 큐에 넣는다.
        • 결과적으로 너비 우선 탐색 방식과 유사하게, 첫 정점에 인접한 노드들을 순차적으로 방문하게 됨
        • 만약 배열에 기록된 현재까지 발견된 가장 짧은 거리보다, 더 긴 거리(루트)를 가진 (노드, 거리)의 경우에는 해당 노드와 인접한 노드간의 거리 계산을 하지 않음
    3. 2번의 과정을 우선순위 큐에 꺼낼 노드가 없을 때까지 반복한다.

코드

  • JS
        class PriorityQueue {
        constructor() {
            this.queue = [];
        }
    
        enqueue(node, priority) {
            this.queue.push({node, priority});
            this.sort();
        }
    
        dequeue() {
            return this.queue.shift();
        }
    
        sort() {
            this.queue.sort((a, b) => a.priority - b.priority);
        }
    
        isEmpty() {
            return !this.queue.length;
        }
    }
    
    function dijkstra(graph, start) {
        let distances = {};
        for(let node in graph) {
            distances[node] = Infinity;
        }
        distances[start] = 0;
    
        let pq = new PriorityQueue();
        pq.enqueue(start, 0);
    
        while(!pq.isEmpty()) {
            let minNode = pq.dequeue();
            let current_node = minNode.node;
            let current_distance = minNode.priority;
    
            if(distances[current_node] < current_distance) {
                continue;
            }
    
            for(let adjacent in graph[current_node]) {
                let distance = current_distance + graph[current_node][adjacent];
    
                if(distance < distances[adjacent]) {
                    distances[adjacent] = distance;
                    pq.enqueue(adjacent, distance);
                }
            }
        }
        return distances;
    }
    다음은 다익스트라 알고리즘을 사용하여 최단 경로를 찾는 JavaScript 코드의 간단한 예입니다. 이 예제에서는 시작점에서 다른 모든 노드까지의 최단 경로를 찾습니다.
       // 우선순위 큐를 최소 힙으로 구현한 클래스입니다.
   class PriorityQueue {
     constructor() {
       this.heap = [];
     }
   
     enqueue(node, priority) {
       this.heap.push([node, priority]);
       this.bubbleUp(this.heap.length - 1);
     }
   
     dequeue() {
       const root = this.heap[0];
       const last = this.heap.pop();
       if (!this.isEmpty()) {
         this.heap[0] = last;
         this.bubbleDown(0);
       }
       return root;
     }
   
     // peek() {
     //   return this.heap[0][1];
     // }
   
     isEmpty() {
       return this.heap.length === 0;
     }
   
     bubbleUp(index) {
       if (index === 0) {
         return;
       }
       const parentIndex = Math.floor((index - 1) / 2);
       const parent = this.heap[parentIndex];
       const child = this.heap[index];
       if (child[1] < parent[1]) {
         this.swap(index, parentIndex);
         this.bubbleUp(parentIndex);
       }
     }
   
     bubbleDown(index) {
       let leftChildIndex = 2 * index + 1;
       let rightChildIndex = 2 * index + 2;
       let smallestChildIndex = leftChildIndex;
       if (
         rightChildIndex < this.heap.length &&
         this.heap[leftChildIndex][1] > this.heap[rightChildIndex][1]
       ) {
         smallestChildIndex = rightChildIndex;
       }
       if (
         smallestChildIndex < this.heap.length &&
         this.heap[smallestChildIndex][1] < this.heap[index][1]
       ) {
         this.swap(index, smallestChildIndex);
         this.bubbleDown(smallestChildIndex);
       }
     }
   
     swap(index1, index2) {
       const temp = this.heap[index1];
       this.heap[index1] = this.heap[index2];
       this.heap[index2] = temp;
     }
   }
   
   function dijkstra(graph, start) {
     let distances = {};
     for (let node in graph) {
       distances[node] = Infinity;
     }
     distances[start] = 0;
   
     let queue = new PriorityQueue();
     queue.enqueue(start, 0);
   
     while (!queue.isEmpty()) {
       let [currentNode, currentDistance] = queue.dequeue();
   
       if (distances[currentNode] < currentDistance) {
         continue;
       }
   
       // 현재 노드의 이웃 노드들을 반복합니다.
       for (let neighbor in graph[currentNode]) {
         // 시작 노드에서 이웃 노드까지의 거리를 계산합니다.
         let newDistance = distances[currentNode] + graph[currentNode][neighbor];
   
         // 만약 이웃 노드까지의 거리가 아직 계산되지 않았거나, 새로 계산한 거리가 기존의 거리보다 짧으면 업데이트합니다.
        if (distances[neighbor] > newDistance) {
           distances[neighbor] = newDistance;
   
           // 업데이트된 거리를 이용해 이웃 노드를 우선순위 큐에 추가합니다.
           queue.enqueue(neighbor, newDistance);
         }
       }
     }
   
     return distances;
   }
   
   // Unit tests
   let graph = {
     A: { B: 2, C: 5, D: 4 },
     B: { A: 2, C: 2, D: 1, E: 6 },
     C: { A: 5, B: 2, F: 3 },
     D: { A: 4, B: 1, E: 4, G: 2 },
     E: { B: 6, D: 4, F: 1, G: 3 },
     F: { C: 3, E: 1, G: 2 },
     G: { D: 2, E: 3, F: 2 },
   };
   
   const result = dijkstra(graph, "A");
   console.log(result);
   // { A: 0, B: 2, C: 4, D: 3, E: 7, F: 7, G: 5 }
    이 코드는 'A' 노드에서 다른 모든 노드까지의 최단 경로를 계산합니다. 그래프는 인접 리스트로 표현되며, 각 노드 간의 거리는 그래프의 가중치로 표현됩니다. 결과는 노드까지의 최단 거리를 나타내는 객체입니다.
  • Python
    import heapq

def dijkstra(graph, start):
    
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = []
    heapq.heappush(queue, [distances[start], start])
    
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        
        if distances[current_node] < current_distance:
            continue
            
        for adjacent, weight in graph[current_node].items():
            distance = current_distance + weight
            
            if distance < distances[adjacent]:
                distances[adjacent] = distance
                heapq.heappush(queue, [distance, adjacent])
                
    return distances
    import heapq

# 탐색할 그래프와 시작 정점을 인수로 전달받습니다.
def dijkstra(graph, start, end):
    # 시작 정점에서 각 정점까지의 거리를 저장할 딕셔너리를 생성하고, 무한대(inf)로 초기화합니다.
    distances = {vertex: [float('inf'), start] for vertex in graph}

    # 그래프의 시작 정점의 거리는 0으로 초기화 해줌
    distances[start] = [0, start]

    # 모든 정점이 저장될 큐를 생성합니다.
    queue = []

    # 그래프의 시작 정점과 시작 정점의 거리(0)을 최소힙에 넣어줌
    heapq.heappush(queue, [distances[start][0], start])

    while queue:
        
        # 큐에서 정점을 하나씩 꺼내 인접한 정점들의 가중치를 모두 확인하여 업데이트합니다.
        current_distance, current_vertex = heapq.heappop(queue)
        
        # 더 짧은 경로가 있다면 무시한다.
        if distances[current_vertex][0] < current_distance:
            continue
            
        for adjacent, weight in graph[current_vertex].items():
            distance = current_distance + weight
            # 만약 시작 정점에서 인접 정점으로 바로 가는 것보다 현재 정점을 통해 가는 것이 더 가까울 경우에는
            if distance < distances[adjacent][0]:
                # 거리를 업데이트합니다.
                distances[adjacent] = [distance, current_vertex]
                heapq.heappush(queue, [distance, adjacent])
    
    path = end
    path_output = end + '->'
    while distances[path][1] != start:
        path_output += distances[path][1] + '->'
        path = distances[path][1]
    path_output += start
    print (path_output)
    return distances

# 방향 그래프
mygraph = {
    'A': {'B': 8, 'C': 1, 'D': 2},
    'B': {},
    'C': {'B': 5, 'D': 2},
    'D': {'E': 3, 'F': 5},
    'E': {'F': 1},
    'F': {'A': 5}
}

print(dijkstra(mygraph, 'A', 'F'))
profile
CHOYEAH
Move fast & break things
이전 포스트

Greedy

다음 포스트

Minimum Spanning Tree

post-custom-banner

0개의 댓글