다익스트라 알고리즘
다익스트라 알고리즘은 각 노드마다 이동할 수 있는 간선이 존재하고, 간선에 가중치(이동거리)가 있을 때 시작 노드부터 각 정점에 있는 노드까지의 최단거리를 계산하는 알고리즘이다.
다익스트라 알고리즘 동작
- 출발 노드와 목적 노드를 설정한다 (A-D)
- 최단 거리 테이블을 생성 후 출발 노드를 넣어준다
- 출발지는 0을, 나머지 모든 노드를 무한에 가까운 수로 최단 거리 테이블을 초기화한다.
- 인접 노드 중 방문한 노드와 방문하지 않은 노드를 구분하고 방문하지 않은 노드 중
가장 가까운(가중치가 적은) 노드를 선택하고 방문처리 한다. - 해당 노드를 거쳐 다음 노드로 가는 거리를 계산해 최단 거리 테이블을 업데이트한다.
- 3~4번의 행동을 반복한다
다익스트라 알고리즘은 최단 경로를 구하는 과정에서 '각 노드에 대한 현재까지의 최단 거리' 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다. 이러한 1차원 리스트를 최단 거리 테이블이라고 한다. 매번 현재 기준으로 인접한 노드를 찾아보고 나중에 더 짧은 거리의 간선이 생기면 더 짧은 거리의 경로를 불러와 4번 동작을 반복한다.
A-D의 거리를 계산했을 때 A-B의 거리는 5, A-C의 거리는 3이므로 테이블엔 각각 5, 3이 들어간다.
이중 가장 거리가 짧은 A-C를 이동하고 A는 방문한 노드로 처리되며 B에서 인접한 노드인 B-D, C에서 인접한 노드인 C-D, C-E를 탐색한다.
여기서 가중치가 적은 C를 택하고 C-D, C-E를 계산하며 각각 8과 7이 나왔다. A-C간의 가중치를 더하면 각각 11, 10이 나오며 이를 가장 작은 수라고 테이블에 넣어준다.
이후 B의 거리에서 계산하고 B-D를 구하면 7이라는 가중치, 그리고 A-B와 더해주면 12가 나온다. 즉 최소치인 10보다 높기 때문에 최소치인 10이 테이블에 업데이트 된다.
D에 도달했지만 E의 최소거리는 A-C-E가 연결된 10임을 알 수 있다.
따라서 최소 거리 테이블은 다음과 같다.
| 노드 | A | B | C | D | E |
|---|---|---|---|---|---|
| 최단거리 | 0 | 5 | 3 | 11 | 10 |
다익스트라 알고리즘 코드
다익스트라 코드는 다음과 같으며 아래 코드는 위의 예시와는 다른 코드이다.
해당 코드는 순차 탐색을 사용하였으며 우선순위 큐를 사용시 보다 효율적인 코드 작성이 가능해진다
public class DijkstraNode
{
public int index; //자기 번호 0,1,2,3 등등
public Vector2 pos; //해당 노드의 좌표
public float distance; //시작점으로부터 현재 노드 까지의 누적 거리
public DijkstraNode parent; //경로 추적용 부모 노드
public DijkstraNode(int _index, Vector2 _pos, float _distance, DijkstraNode _parent = null)
{
index = _index;
pos = _pos;
distance = _distance;
parent = _parent;
}
}
public class DijkstraExample
{
private void Dijkstra()
{
int n = 4; //노드 갯수
int startIndex = 0; //시작 노드 인덱스
int goalIndex = 3; //목표 노드 인덱스
//각 노드에 좌표 설정해주기
Vector2[] position = new Vector2[4]
{
new(0,0),
new(1,0),
new(0,1),
new(1,1)
};
//그래프 구성
List<(int to, float cost)>[] graph = new List<(int to, float cost)>[n];
for (int i =0; i < n; i++)
{
graph[i] = new List<(int to, float cost)>();
}
//비용 정보 추가
graph[0].Add((1, 1)); //A->B 코스트가 1
graph[0].Add((2, 4)); //A->C 코스트가 4
graph[1].Add((2, 2)); //B->C 코스트가 2
graph[1].Add((3, 6)); //B->D 코스트가 6
graph[2].Add((3, 4)); //C->D 코스트가 3
//각 노드까지의 최소 거리 저장 배열
float[] distances = new float[n];
for(int j =0; j<n; j++)
{
distances[j] = float.MaxValue;
}
//시작 지점
distances[startIndex] = 0;
//방문 여부 저장 배열
bool[] visted = new bool[n];
//탐색 대기 리스트
var openList = new List<DijkstraNode>();
//시작 지점 추가
openList.Add(new DijkstraNode(startIndex, position[startIndex], 0));
while (openList.Count > 0)
{
//거리 기준으로 정렬
openList.Sort((a, b) => a.distance.CompareTo(b.distance));
//최소 거리 노드 선택
var current = openList[0];
//선택한 애는 탐색 대상에서 제외시켜주기
openList.RemoveAt(0);
//방문한 노드는 스킵하기
if (visted[current.index])
{
continue;
}
//방문처리
visted[current.index] = true;
//목표 노드 도착시 경로 복원
if(current.index == goalIndex)
{
var path = new List<int>();
var temp = current;
//부모따라 역 추적
while(temp != null)
{
path.Add(temp.index);
temp = temp.parent;
}
//D - C - B - A
path.Reverse();
//A - B - C -D
Debug.Log("다익스트라 패스 " + string.Join("->",path));
Debug.Log("총 경로는 " + current.distance);
break;
}
foreach(var neighbor in graph[current.index])
{
//이미 방문한 노드는 패스
if (visted[neighbor.to])
{
continue;
}
//현재 노드까지의 거리 + 간선 비용
float t = current.distance + neighbor.cost;
//더 짧은 경로 발견시
if (t < distances[neighbor.to])
{
distances[neighbor.to] = t;
//새로운 노드 추가
openList.Add(new DijkstraNode(neighbor.to, position[neighbor.to], t, current));
}
}
}
}
} 다익스트라 알고리즘 특징
-
가능한 모든 경로를 탐색하는 길찾기에 비해 보다 효율적인 경로 탐색이 가능하다
-
모든 노드의 정점을 탐색하기 때문에 길찾기의 최고 효율을 보장하지는 않는다.
-
다익스트라 알고리즘은 노드 간선의 거리가 음수일 때는 사용이 불가능하다. (음수 값을 최솟값으로 계산하여 무한 반복하기 때문)
-
노드의 갯수가 많아질수록 탐색하는 시간이 늘어난다.
