캐나다 IT 코딩 Dijkstra

Dijkstra(다익스트라) 알고리즘은 그래프에서 두 노드 사이의 최단 경로를 찾기 위한 알고리즘입니다. 음수가 아닌 간선 가중치를 가진 그래프에서 작동하며, 시작 노드로부터 그래프의 다른 모든 노드까지의 경로들을 찾아 비교합니다.

Dijkstra 알고리즘의 정의

Dijkstra 알고리즘을 이해하기 위해서는 우선 BFS (Breadth-first search) 알고리즘을 학습하는 것을 추천드립니다. 이를 통해 우선 Graph라는 데이터 형식과 Node, Edge 등에 대해 확실히 이해를 할 수 있고, 이 두 가지 알고리즘의 비교를 통해 구체적으로 이해할 수 있게 됩니다.

Dijkstra 알고리즘과 BFS(Breadth-first search) 알고리즘은 둘 다 그래프에서 최단 경로를 찾는 데 사용되는 알고리즘입니다. 그러나 두 알고리즘은 목적과 작동 방식에서 차이가 있습니다.

 

Dijkstra 알고리즘과 BFS(Breadth-first search) 알고리즘 비교

Dijkstra 알고리즘

• 다익스트라 알고리즘은 가중치가 있는 그래프 (Weighed Graph)에서 최단 경로를 찾는 데 사용되는데 여기에서 최단 경로는 가중치가 적용됨을 주의해야 합니다. 가중치의 의미는 A라는 노드에서 B라는 노드까지의 값의 명시를 의미합니다. 예를 들어 걸리는 시간, 비용 등을 생각할 수 있습니다
• 음수 가중치를 허용하지 않는 그래프에서 사용됩니다. 음수 가중치까지 고려하는 알고리즘은 다른 알고리즘 기법(Bellmen-Forward 알고리즘)을 이용해야 합니다.
• 현재까지 방문한 노드까지의 최단 거리를 유지하면서 다음으로 방문할 노드를 선택합니다.
• 알고리즘의 종료 시점은 모든 노드를 방문하거나 목적지 노드에 도달하는 경우입니다.

BFS 알고리즘

• BFS 알고리즘은 그래프를 너비 우선으로 탐색하는 데 사용됩니다. 너비 우선으로 탐색하는 것의 의미는 Node와 Node 사이의 가중치가 없기 때문에 그런 값을 제외하고 목적지까지 최소로 소요되는 Node 간의 연결 고리를 찾아낸다는 의미입니다.
• 시작 노드에서 시작하여 인접한 노드를 먼저 방문합니다.
• 가중치가 없는 그래프(Unweighed Graph)에서 사용됩니다.
• 모든 이웃 노드를 방문한 후에는 그 이웃 노드의 이웃 노드를 방문합니다.
• 큐(Queue)를 사용하여 방문할 노드를 저장하고, 이미 방문한 노드를 추적하기 위해 집합(Set)을 사용합니다.
• BFS 알고리즘은 시작 노드에서 도달 가능한 모든 노드를 방문하고 처리한 후에야 다음 레벨의 노드로 넘어갑니다.

따라서 Dijkstra 알고리즘은 가중치가 있는 그래프에서 최단 경로를 찾는 데 사용되는 반면, BFS 알고리즘은 그래프를 너비 우선으로 탐색하는 데 사용됩니다. 다른 표현으로 한다면 BFS는 A 지점에서 Z 지점까지의 걸리는 소요시간에 상관없이 최단 경로를 찾게 되지만 Dijjstra 알고리즘은 소요시간을 고려하기 때문에 여기에서 의미하는 최단 경로는 가장 빠르게 도달하는 경로를 찾는데 이용됩니다.

Dijkstra 알고리즘의 동작 과정

1. 알고리즘을 초기화하고 그래프의 모든 노드에 대해 잠정적인 거리 값을 할당합니다. 시작 노드는 거리 0으로 할당되고, 모든 다른 노드는 무한대의 거리로 할당됩니다.
2. 시작 노드를 현재 노드로 설정합니다.
3. 현재 노드에 대해 모든 이웃 노드를 고려하고, 현재 노드를 통해 이웃 노드의 잠정적인 거리를 계산합니다. 잠정적인 거리가 현재 할당된 값보다 작은 경우 이웃 노드의 잠정적인 거리를 업데이트합니다.
4. 모든 이웃 노드를 방문한 후, 현재 노드를 방문한 것으로 표시합니다.
5. 목적지 노드가 방문된 경우 또는 방문되지 않은 노드 중 가장 작은 잠정적인 거리가 무한대인 경우, 알고리즘을 중지합니다.
6. 그렇지 않은 경우, 잠정적인 거리가 가장 작은 방문되지 않은 노드를 다음 현재 노드로 선택하고 3단계로 돌아갑니다.

3단계부터 6단계까지 반복함으로써, 알고리즘은 그래프의 모든 노드를 방문하고 시작 노드부터 각 노드까지의 최단 경로를 결정합니다. 다익스트라 알고리즘은 경로 설정 프로토콜, 네트워크 분석, 지도 또는 GPS 시스템에서의 경로 탐색 등 다양한 응용 분야에서 널리 사용됩니다.

Dijkstra 코딩 예제

import heapq

def dijkstra(graph, start_node):
    # Create a priority queue for nodes to visit
    queue = [(0, start_node)]
    # Create a dictionary to keep track of distances
    distances = {node: float('inf') for node in graph}
    distances[start_node] = 0

    while queue:
        # Dequeue the node with the smallest distance
        current_distance, current_node = heapq.heappop(queue)
        # Ignore outdated entries in the priority queue
        if current_distance > distances[current_node]:
            continue
        # Explore the neighbors of the current node
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            # Update the distance of the neighbor if a shorter path is found
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                # Enqueue the neighbor with the updated distance
                heapq.heappush(queue, (distance, neighbor))

    return distances

# Example graph
graph = {
    'A': {'B': 5, 'C': 2},
    'B': {'A': 5, 'C': 1, 'D': 3},
    'C': {'A': 2, 'B': 1, 'D': 2},
    'D': {'B': 3, 'C': 2}
}

start_node = 'A'

# Find the shortest distances using Dijkstra's algorithm
shortest_distances = dijkstra(graph, start_node)

# Print the shortest distances
for node, distance in shortest_distances.items():
    print(f"Shortest distance from {start_node} to {node}: {distance}")

이 예제에서는 인접 사전으로 표현된 그래프가 있습니다. 다익스트라 알고리즘을 사용하여 시작 노드에서 모든 다른 노드까지의 최단 거리를 찾고 싶습니다. 이 알고리즘은 우선순위 큐(최소 힙)와 거리를 추적하기 위한 사전으로 구현됩니다. 모든 거리를 무한대로 초기화하고 시작 노드만 0으로 설정합니다. 가장 작은 거리를 가진 노드를 계속해서 빼내어 그 이웃을 탐색합니다. 더 짧은 경로가 발견되면 거리를 업데이트하고 업데이트된 거리로 이웃을 우선순위 큐에 넣습니다. 우선순위 큐가 비어질 때까지 알고리즘을 계속합니다. 마지막으로, 우리는 시작 노드에서 그래프의 각 노드로 가는 최단 거리를 출력합니다.

 

Dijkstra 작동 기본 이미지

최단 경로를 찾기 위한 Dijkstra 알고리즘 적용

 

위 이미지는 Dijkstra 알고리즘의 작동 예시입니다. 알고리즘은 시작 노드에서 다른 모든 노드까지의 최단 경로를 찾기 위해 사용됩니다. 알고리즘은 우선순위 큐와 거리를 추적하기 위한 사전으로 구현됩니다. 시작 노드에서 시작하여 가장 가까운 이웃 노드로 이동하고, 그 이웃 노드를 통해 더 가까운 이웃 노드로 이동하는 과정을 반복합니다. 알고리즘이 종료되면 그래프의 모든 노드까지의 최단 경로가 결정됩니다.

 

Dijkstra 알고리즘의 장, 단점

Dijkstra 알고리즘의 장점:

• 최단 경로 찾기: Dijkstra 알고리즘은 가중치가 있는 그래프에서 두 노드 사이의 최단 경로를 찾는 데 사용됩니다.
• 음수 가중치 제한: Dijkstra 알고리즘은 음수 가중치를 허용하지 않는 그래프에서 사용됩니다. 음수 가중치를 고려해야 하는 경우에는 다른 알고리즘 기법이 필요합니다.
• 정확성: Dijkstra 알고리즘은 최단 경로를 정확하게 찾습니다.

Dijkstra 알고리즘의 단점:

• 시간 복잡도: Dijkstra 알고리즘은 그래프의 모든 노드를 방문하므로 시간 복잡도가 O(V^2)입니다. 그러나 우선순위 큐를 사용하여 최소 거리를 찾는 데 필요한 시간을 줄일 수 있습니다.
• 공간 복잡도: Dijkstra 알고리즘은 각 노드까지의 최단 거리를 추적하기 위해 메모리를 많이 사용합니다. 큰 그래프에서는 공간 복잡도가 증가할 수 있습니다. 따라서 Dijkstra 알고리즘은 최단 경로를 찾는 정확한 알고리즘이지만, 시간과 공간의 제약이 있을 수 있습니다.
•  

코딩 테스트 실제 기출문제 - Dijkstra 알고리즘

캐나다 IT 회사에서 출제된 BFS 알고리즘 관련 실제 기출문제를 소개합니다. 영문 자체를 한글로 굳이 번역해서 소개하지 않는 이유는 이런 패턴에 익숙해지셔야 하기 때문입니다. 그리고 Solution을 보시기 전에 반드시 우선 문제 자체를 풀어 보시고 접근하시기 바랍니다.

 

Question: To find the shortest distances between cities using Dijkstra's algorithm, you can utilize a graph data structure implemented with a hash table. This graph should include information about each city and the distances between them. After implementing the algorithm, you can print the shortest distances from the start node to each city.

 

Example

graph representing cities in Canada and their distances.

graph = {
    'Vancouver': {'Calgary': 605, 'Edmonton': 815, 'Winnipeg': 2145},
    'Calgary': {'Vancouver': 605, 'Edmonton': 296, 'Winnipeg': 1327},
    'Edmonton': {'Vancouver': 815, 'Calgary': 296, 'Winnipeg': 1212},
    'Winnipeg': {'Vancouver': 2145, 'Calgary': 1327, 'Edmonton': 1212}
}

start_node = 'Vancouver'

# Find the shortest distances using Dijkstra's algorithm
shortest_distances = dijkstra(graph, start_node)

 

# Print the shortest distances from the start node to each city
for city, distance in shortest_distances.items():
    print(f"Shortest distance from {start_node} to {city}: {distance}")

 

Example Output:

Shortest distance from Vancouver to Vancouver: 0
Shortest distance from Vancouver to Calgary: 605
Shortest distance from Vancouver to Edmonton: 815
Shortest distance from Vancouver to Winnipeg: 1545

 

Solution

import heapq

def dijkstra(graph, start_node):
    # Create a priority queue for nodes to visit
    queue = [(0, start_node)]
    # Create a dictionary to keep track of distances
    distances = {node: float('inf') for node in graph}
    distances[start_node] = 0

    while queue:
        # Dequeue the node with the smallest distance
        current_distance, current_node = heapq.heappop(queue)
        # Ignore outdated entries in the priority queue
        if current_distance > distances[current_node]:
            continue
        # Explore the neighbors of the current node
        for neighbor, distance in graph[current_node].items():
            total_distance = current_distance + distance
            # Update the distance of the neighbor if a shorter path is found
            if total_distance < distances[neighbor]:
                distances[neighbor] = total_distance
                # Enqueue the neighbor with the updated distance
                heapq.heappush(queue, (total_distance, neighbor))

    return distances

 

---

 

캐나다 IT 코딩 Breadth-first search

 

캐나다 IT 코딩 Hash Table