목록2026/06/10 (1)

와드의 블로그

[코드트리] 다익스트라 알고리즘 쉽게 이해하기 (개념부터 구현까지 총정리)

1. 다익스트라 알고리즘은 무엇일까?다익스트라 알고리즘은 그래프 내의 한 정점(시작점)에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘입니다.현실 세계에서 내비게이션이 목적지까지의 최소 시간 경로나 최소 비용 경로를 찾을 때 사용하는 알고리즘의 뼈대가 되기도 합니다. 단, 이 알고리즘은 간선의 가중치가 음수가 아닐 때만 정상적으로 동작한다는 중요한 제약 조건이 있습니다. 음수 간선이 존재할 경우에는 벨만-포드(Bellman-Ford) 알고리즘을 사용해야 합니다.2. 동작 과정다익스트라 알고리즘은 '매 순간 가장 비용이 적은 노드를 선택한다'는 그리디(Greedy) 알고리즘과, '이전에 계산해둔 최단 거리 값을 활용한다'는 동적 계획법(DP)의 아이디어가 결합되어 있습니다.기본적인 동작 과정은 다음과..
TIL 2026. 6. 10. 16:05
이전 Prev 1 Next 다음