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

다익스트라(Dijkstra)

• 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘
• 특정한 노드에서 출발해 연결되어 있는 다른 모든 노드로 가는 최단 경로를 구하기 위한 알고리즘
• 0보다 작은 값을 가지는 음의 간선이 없어야 정상적으로 동작
• 보통 우선 순위 큐를 구현하기 위해 사용되는 heapq 라이브러리를 활용해서 구현
• GPS 소프트웨어의 기본 알고리즘으로 채택

 

 

 

과정

1. 출발 노드를 설정
2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장
3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택
4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신
5. 위의 3번 ~ 4번 과정을 반복

동작 단계에 대한 예시는 아래 게시물이 잘 정리되어 있으니 참고하면 좋을 것 같다!

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

 

 

 

파이썬 코드

# heapq를 활용한 dijkstra

import heapq
from collections import defaultdict


def dijkstra(graph, start):
    distance = defaultdict(lambda: int(1e9))
    distance[start] = 0
    h = []
    heapq.heappush(h, (distance[start], start))

    while h:
        now_dist, now_node = heapq.heappop(h)  # dist : 거리, node : 노드

        if distance[now_node] < now_dist:  # 기존 거리 보다 멀다면 고려할 필요 없음
            continue
        
        for next_node, next_dist in graph[now_node].items():
            cost = distance[now_node] + next_dist
            if cost < distance[next_node]:
                distance[next_node] = cost
                heapq.heappush(h, (cost, next_node))

    return dict(distance)

# 예시 데이터
data = {
    '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(data, 'A'))  # {'A': 0, 'B': 6, 'C': 1, 'D': 2, 'E': 5, 'F': 6}

 

 

 

 

 

 

https://lu-coding.tistory.com/64

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

https://m.blog.naver.com/ndb796/221234424646

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

https://velog.io/@717lumos/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BCDijkstra-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

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