다익스트라 알고리즘 원리와 최단 경로 탐색 쉽게 이해하기

핵심 메시지

• 1956년 다익스트라는 로테르담에서 흐로닝언까지의 최단 경로를 고민하다, 카페에서 커피를 마시는 약 20분 만에 알고리즘의 핵심 논리를 완성했다.
• 알고리즘은 도시와 도로를 노드(정점)와 가중치가 있는 간선으로 이루어진 그래프로 추상화해 다룬다.
• 출발 노드에서 자기 자신까지의 거리는 0, 나머지는 무한대로 두고, 아직 방문하지 않은 노드 중 누적 거리가 가장 작은 노드를 차례로 골라 이웃의 거리를 갱신한다.
• 매 단계에서 그 순간 가장 좋아 보이는 선택을 반복하기 때문에 '탐욕(greedy) 알고리즘'으로 분류된다.
• 파이썬 구현에서는 우선순위 큐(최소 힙)로 가장 가까운 노드를 즉시 꺼내 효율을 높이고, 기록해 둔 이전 노드를 역추적해 실제 최단 경로를 복원한다.

쉽게 이해하기

이 영상은 1956년 네덜란드의 프로그래머 에츠허르 다익스트라가 어떻게 최단 경로 알고리즘을 떠올렸는지에서 출발한다. 그는 새 컴퓨터 ARMAC의 성능을 보여줄 문제로 '두 지점 사이의 가장 효율적인 경로 찾기'를 골랐고, 여자친구와 쇼핑 중 카페에 앉아 커피를 마시던 약 20분 사이에 핵심 논리를 머릿속으로 완성했다. 알고리즘은 3년 뒤인 1959년 정식 논문으로 발표됐다.

알고리즘을 이해하려면 먼저 '그래프'라는 자료구조가 필요하다. 도시는 노드로, 도시를 잇는 도로는 간선으로 표현되며, 각 간선에는 거리나 시간 같은 비용을 나타내는 '가중치'가 붙는다. 이렇게 세상을 노드와 간선으로 바꾸면 도로뿐 아니라 SNS 사용자, 물류 창고, 네트워크 라우터, 게임 타일 등 연결된 무엇에나 같은 방법을 적용할 수 있다.

동작은 이렇다. 출발 노드까지의 거리는 0, 나머지는 무한대로 초기화한다. 그다음 아직 방문하지 않은 노드 가운데 누적 거리가 가장 작은 노드를 골라 방문하고, 그 이웃들로 가는 새 거리가 지금 기록된 값보다 짧을 때만 거리와 '이전 노드'를 갱신한다. 영상의 예시에서는 A에서 D까지의 최단 거리가 7(A→B→D)로 계산됐다.

파이썬에서는 이 과정을 우선순위 큐(최소 힙)로 구현한다. 매번 전체 목록을 훑는 대신 출발점에서 가장 가까운 노드를 곧바로 꺼내 방문하고, 방문 집합으로 중복을 막는다. 마지막에는 각 노드의 '이전 노드' 기록을 도착지에서부터 거꾸로 따라가며 경로를 복원한 뒤 순서를 뒤집어 최단 경로를 얻는다.

흥미롭게도 다익스트라는 종이와 연필 없이 순전히 머릿속으로 알고리즘을 설계했다고 밝혔다. 그는 그런 제약이 '피할 수 있는 복잡성'을 모두 없애도록 강제했다고 회고했다. 이 단순함과 강력한 원리가 결합해 GPS 내비게이션·네트워크 라우팅 등 오늘날 수많은 시스템의 토대가 됐고, 그는 1972년 튜링상을 받았다.

주요 인사이트

• 문제를 특정한 두 도시가 아니라 '임의의 두 지점'으로 일반화한 순간, 하나의 문제 풀이가 범용 도구로 바뀌었다.
• 노드와 간선이라는 추상화 덕분에 도로 지도를 넘어 SNS·물류·네트워크·게임 등 연결 구조가 있는 어떤 영역에도 그대로 적용된다.
• 우선순위 큐(최소 힙)를 쓰면 다음에 방문할 노드를 고를 때 전체를 뒤지지 않고 가장 가까운 노드를 즉시 얻어 성능이 좋아진다.
• 다익스트라가 종이 없이 머릿속으로 설계하며 얻은 교훈처럼, 제약은 때로 불필요한 복잡성을 걷어내 단순한 해법을 이끌어낸다.

자주 묻는 질문

관련 AI 소식