Dijkstra 알고리즘: 모든 시작점에서 최단 경로를 구하는 방법 > 경로 계획 및 자율 주행 알고리즘

• 목록

지난 시간에는 A* 알고리즘이 휴리스틱을 활용하여 시작점에서 목표점까지 최단 경로를 효율적으로 찾아내는 고전적인 지능형 탐색 방법임을 알아보았습니다. 이제 A* 알고리즘의 기반이 되면서, 단일 시작점에서 모든 다른 노드까지의 최단 경로를 구하는 데 특화된 또 다른 고전적인 경로 탐색 알고리즘인 Dijkstra(다익스트라) 알고리즘에 대해 파헤쳐 보겠습니다.

다익스트라 알고리즘은 "음의 가중치가 없는 그래프에서 최단 경로를 찾아내는 데 사용되는 대표적인 알고리즘"입니다.  마치 낯선 도시에서 출발점으로부터 모든 관광지까지의 가장 빠른 길을 알아내는 것과 같습니다. 이 알고리즘은 A*처럼 목표 지점까지의 '추정 비용'을 사용하지 않고, 오직 '현재까지의 실제 비용'만을 고려하는 탐욕적인(Greedy) 방식으로 탐색을 진행합니다. 로봇이 미리 구축된 지도 위에서 여러 목표 지점들 중 하나를 선택해야 하거나, 네트워크 경로 최적화와 같이 '시작점으로부터 모든 지점'까지의 최단 거리가 필요한 상황에서 다익스트라 알고리즘은 매우 유용하게 활용될 수 있습니다. 이 설명을 통해 다익스트라 알고리즘이 무엇이며, 어떻게 모든 시작점에서 최단 경로를 구하는지, 그 원리와 작동 방식, 그리고 로봇 개발에서의 활용은 무엇인지 자세히 파헤쳐 보겠습니다.

로봇이 "현재 위치에서 창고 내 모든 픽업 지점까지의 최단 거리를 파악하여 어떤 순서로 픽업할지 최적의 동선을 계획해야 하는" 상황이라면, 다익스트라 알고리즘은 로봇에게 모든 픽업 지점까지의 최단 거리를 제공하여 최적의 동선을 결정하는 데 도움을 줍니다.

1. Dijkstra(다익스트라) 알고리즘이란 무엇인가?

다익스트라 알고리즘은 "음의 가중치를 가지지 않는(Non-negative Weights) 방향 그래프 또는 무방향 그래프에서, 단일 시작점(Source Node)에서 그래프의 다른 모든 노드까지의 최단 경로를 찾아내는 알고리즘"입니다. 

배경: 1956년 컴퓨터 과학자 에츠허르 다익스트라(Edsger W. Dijkstra)가 고안했습니다.

탐욕적인(Greedy) 방식: 현재 상태에서 가장 최적이라고 판단되는 선택(가장 짧은 경로)을 반복적으로 하여 전체 최적해를 찾아나가는 방식입니다.

2. 다익스트라 알고리즘의 핵심 원리: 최단 거리 갱신

다익스트라 알고리즘은 다음과 같은 핵심 원리를 바탕으로 최단 경로를 찾아나갑니다.

거리 배열 초기화: 시작 노드로부터 각 노드까지의 최단 거리를 저장하는 dist 배열을 초기화합니다. 시작 노드까지의 거리는 0으로, 나머지 노드까지의 거리는 무한대(∞)로 설정합니다.

방문 여부: 각 노드의 방문 여부를 기록합니다.

최소 거리 노드 선택: 아직 방문하지 않은 노드 중에서 시작 노드로부터의 거리가 가장 짧은 노드를 선택합니다.

거리 갱신 (Relaxation): 선택된 노드를 경유하여 인접 노드까지 가는 경로가 기존에 알려진 최단 경로보다 짧다면, 인접 노드까지의 최단 거리를 갱신합니다. 

3. 다익스트라 알고리즘의 작동 방식 (단계별 설명)

알고리즘은 Open List (우선순위 큐)를 사용하여 다음 단계를 진행합니다.

초기화:

dist 배열의 모든 값을 무한대(∞)로 설정하고, dist[시작 노드] = 0으로 설정합니다.

visited 배열의 모든 값을 False로 설정합니다.

우선순위 큐(Priority Queue)에 (0, 시작 노드)를 삽입합니다. (비용, 노드 순)

탐색 반복:

우선순위 큐가 빌 때까지 다음을 반복합니다.

우선순위 큐에서 **현재까지의 거리가 가장 짧은 노드(current_dist, current_node)**를 추출합니다.

만약 current_node가 이미 방문한 노드라면 건너뜁니다.

current_node를 visited = True로 표시합니다.

만약 current_dist가 dist[current_node]보다 크다면 (이미 더 짧은 경로를 찾았다면), 건너뜁니다. (이것은 우선순위 큐에 중복된 노드가 들어가 있을 때 발생할 수 있습니다.)

이웃 노드 갱신 (Relaxation):

current_node의 모든 인접 노드(neighbor)에 대해 다음을 수행합니다.

새로운 거리 = dist[current_node] + current_node에서 neighbor까지의 가중치

만약 새로운 거리가 dist[neighbor]보다 작다면 (더 짧은 경로를 찾았다면):

dist[neighbor] = 새로운 거리

우선순위 큐에 (새로운 거리, neighbor)를 삽입합니다.

4. 다익스트라 알고리즘의 주요 특징 및 한계

4.1. 비음수 간선 가중치 (Non-negative Edge Weights):

매우 중요: 다익스트라 알고리즘은 간선 가중치(edge weight)가 음수이면 올바르게 작동하지 않습니다.  음수 가중치가 있는 경우 벨만-포드(Bellman-Ford) 알고리즘 등을 사용해야 합니다.

이유: 이미 처리된 노드의 최단 거리는 갱신되지 않는다는 전제가 있는데, 음수 간선이 있으면 이 전제가 깨질 수 있습니다.

4.2. 최단 경로 보장:

음의 가중치가 없는 그래프에서는 항상 시작 노드에서 모든 다른 노드까지의 최단 경로를 보장합니다.

4.3. 시간 복잡도:

우선순위 큐를 사용할 경우, V개의 노드와 E개의 간선을 가진 그래프에서 O(E log V) 또는 O(E + V log V)의 시간 복잡도를 가집니다. (구현 방식에 따라 다름)

5. 다익스트라 알고리즘의 장점과 단점

장점:

범용성: 다양한 종류의 그래프(방향/무방향)에 적용 가능합니다.

최단 경로 보장: 조건(비음수 간선)만 만족하면 항상 최단 경로를 찾습니다.

간단한 개념: 알고리즘의 기본 개념은 비교적 직관적입니다.

단점:

음수 가중치 처리 불가: 가장 큰 제약 조건입니다.

효율성: 특정 목표 노드까지의 최단 경로만 필요한 경우, A* 알고리즘이 좋은 휴리스틱을 사용하면 더 효율적일 수 있습니다. 다익스트라는 모든 노드까지의 최단 경로를 구하기 때문입니다.

메모리 사용: 대규모 그래프의 경우 dist 배열과 우선순위 큐가 많은 메모리를 사용할 수 있습니다.

6. 로봇 개발에서 다익스트라 알고리즘의 활용

다익스트라 알고리즘은 로봇의 전역 경로 계획을 비롯하여 다양한 분야에서 활용됩니다.

6.1. 전역 경로 계획 (Global Path Planning):

로봇이 미리 구축된 지도(SLAM을 통해 생성) 위에서 시작점에서 목표점까지의 최단 경로를 찾을 때 활용됩니다. 특히 로봇이 이동할 수 있는 노드와 간선으로 표현되는 격자 지도(Grid Map)에서 각 간선의 비용(이동 시간, 에너지 소모)이 음수가 아닌 경우에 적용 가능합니다.

A*와의 비교: 특정 목표 지점 하나만으로 최단 경로를 찾는 경우 A*가 더 빠를 수 있지만, 로봇이 여러 후보 목표 지점 중 최적의 하나를 선택해야 할 때(예: 창고 내 모든 픽업 지점 중 가까운 순서로 방문)는 다익스트라가 모든 노드까지의 최단 거리를 제공하므로 유용합니다.

6.2. 네트워크 경로 최적화:

로봇 통신 네트워크: 다수의 로봇이나 센서 노드로 구성된 통신 네트워크에서 데이터 패킷이 최단 시간 또는 최소 홉(Hop) 수로 전송될 경로를 결정하는 데 사용됩니다.

물류 시스템: 최단 경로로 물류를 배송하거나, 네트워크 내에서 로봇 간의 최단 상호작용 경로를 찾는 데 활용됩니다.

6.3. 자원 할당 및 스케줄링:

생산 라인이나 창고에서 로봇들의 작업을 최적의 순서로 스케줄링하거나, 로봇에게 자원을 효율적으로 할당하기 위해 최단 비용 경로를 계산할 때 응용될 수 있습니다.

6.4. 비용 맵(Cost Map) 기반 계획:

로봇 내비게이션에서 충돌 위험 지역, 경사로 등 이동 비용이 다른 환경을 비용 맵으로 표현하고, 이 맵 위에서 다익스트라를 적용하여 최단 비용 경로를 찾습니다.

다익스트라 알고리즘은 음의 가중치가 없는 그래프에서 단일 시작점으로부터 모든 다른 노드까지의 최단 경로를 찾아내는 고전적인 탐욕(Greedy) 알고리즘입니다. 시작 노드에서 가장 가까운 노드를 반복적으로 선택하고, 이 노드를 경유하여 인접 노드까지의 거리를 갱신하는 방식으로 작동합니다.

로봇 개발에서 다익스트라 알고리즘은 전역 경로 계획의 핵심을 이루며, 로봇이 미리 구축된 지도 위에서 여러 목표 지점들까지의 최단 거리를 효율적으로 파악하고, 네트워크 경로 최적화, 자원 할당 등 다양한 최적화 문제에 활용됩니다. 다익스트라 알고리즘의 원리와 작동 방식을 완벽하게 이해하고 이를 로봇에 적용하는 것은 로봇에게 '시작점에서부터 모든 목적지까지의 가장 효율적인 길을 찾아내는 지능'을 불어넣어 미래의 자율 로봇 시대를 선도하는 중요한 발판이 될 것입니다.