다익스트라 알고리즘-개념1

최단경로 알고리즘의 종류

1. 다익스트라 알고리즘

2. 벨만-포드 알고리즘

3. 플로이드-워셜 알고리즘

 

다익스트라 알고리즘이란

다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘이다.

흔히 인공위성 GPS 소프트웨어에서 가장 많이 사용 되는데, 이는 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려주기에 주로 사용된다.

다익스트라 알고리즘의 동작 단계

1. 출발 노드와 도착 노드를 설정한다.
2.  '최단 거리 테이블'을 초기화한다.
3.  현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. 그 노드를 방문 처리한다.
4. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 '최단 거리 테이블'을 업데이트한다.
5. 3번과 4번의 과정을 반복한다.

 

'최단 거리 테이블'은 1차원 배열로, N개 노드까지 오는 데 필요한 최단 거리를 기록한다.
N개(1부터 시작하는 노드 번호와 일치시키려면 N + 1개) 크기의 배열을 선언하고 큰 값을 넣어 초기화시킨다.

'노드 방문 여부 체크 배열'은 방문한 노드인지 아닌지 기록하기 위한 배열로, 크기는 '최단 거리 테이블'과 같다. 기본적으로는 False로 초기화하여 방문하지 않았음을 명시한다.

 

이해를 돕기 위한 예시

아래와 같은 그래프가 존재할 때 다익스트라 알고리즘을 통해 최단시간을 구해보자.

 

프로그래밍을 활용해 최단거리를 구하려면 1차원 배열을 사용하지만 컴퓨터 내에서 처리할때는
이차원 배열 형태로 처리한다.

 

	1	2	3	4	5	6
1	0	2	5	1	inf	inf
2	2	0	3	2	inf	inf
3	5	3	0	3	1	5
4	1	2	3	0	1	inf
5	inf	inf	5	1	0	2
6	inf	inf	5	inf	2	0

 

1번 노드를 기준으로 잡고 최단 경로를 구해보자.

1번 노드와 연결된 번호는 2,3,4번이다. 하지만 2번은 2분이 소요되고, 3번은 5분이, 4번은 1분이 소요가 되기 때문에 가장 최단시간이 걸리는 번호는 4번이다.

 

0

2

5

1

inf

inf

 

근데 위의 그래프를 보면 5로 가는 최소비용은 inf이지만 4를 거쳐 5로 가는 비용은 2이므로 최소 비용을 갱신해준다.

또한 4를 거쳐서 3으로 가는 경우 비용이 4이므로 기존보다 작기 때문에 이 또한 갱신해준다

 

0

2

4

1

2

inf

 

이제 4번 다음으로 비용이 적은 노드는 2번 노드이다.

하지만 2번 노드를 통해서는 갱신되는 경우가 없기 때문에 배열은 그대로 유지한다

 

2번 노드 다음에는 5번 노드(값 : 2)의 비용이 가장 적다.

5번을 거쳐서 가는 경우에 3번 비용이 3, 6으로 가는비용은 4가 되므로 최단 경로의 값을 갱신해준다.

 

0

2

3

1

2

4

 

 

이러한 방식으로 3번, 6번 노드를 방문하여 계산을 하면 최종적으로 아래와 같은 배열이 완성된다

 

0

2

3

1

2

4