다익스트라 알고리즘(Dijskstra Algorithm)

정리

1. 에지의 가중치가 양수인 연결된 그래프에서 사용

2. 한 정점으로부터 연결된 모든 정점에 대한 최단 경로를 구하는 알고리즘

3. 욕심쟁이 알고리즘(Greedy Algorithm)

 

V : 정점들의 집합

D[v] : 시작정점 s로부터 정점 v까지의 최단거리

S : 시작정점 s로부터 최단 경로를 찾은 정점들의 집합

 

다익스트라 알고리즘은 매 선택에서 최적의 답을 선택하여 적합한 결과를 도출하는 욕심쟁이 알고리즘을 기반으로 두고있다. 여기서 매 선택은 연결된 노드들 중 탐색을 할 노드를 선택하는 과정이며, 최적의 답은 연결된 노드들 중에서 거리가 최소인 노드이다. 다익스트라 알고리즘은 시작 노드를 기준으로 모든 노드의 최단 거리를 구하는 알고리즘으로 시작 노드의 거리를 0, 나머지의 거리는 무한으로 설정하고, 시작 노드를 기준으로 탐색을 시작한다. 매 탐색의 선택은 아래와 같은 순서로 진행된다.

탐색완료된 노드의 집합 S와 연결된 노드들 중에서 거리가 가장 짧은 노드 N를 선택한다.
N과 연결된 노드들(K)의 거리를 구한다.
if 시작노드로부터 K의 길이가 이미 존재한다:
	if 시작노드부터 K의 길이>(시작노드부터 N까지 길이+N부터 K까지 길이):
    	시작노드부터 K까지 경로 길이=시작노드부터 N까지 길이+N부터 K까지 길이
elif 시작 노드로부터 K의 거리가 아직 구해지지 않았다:
	해당 노드 경로 길이=(시작노드부터 N까지의 길이)+(N부터 K까지의 길이)

이러한 탐색은 모든 노드가 탐색 완료 상태가 될 때까지 진행하며, 노드의 연결은 2차원 배열이나 Linked List로 구현할 수 있다. 

 

 

 

알고리즘 프로세스

1. 초기화 및 시작노드 설정

각 노드까지의 거리를 의미하는 D[]는 모든 요소의 값을 무한으로 초기화한다. 또한 경로 탐색 완료 노드를 저장하는 집합 S를 생성한다.

시작 노드를 집합 S에 추가하고 D[시작노드]의 값을 0으로 변경한다. 

2. S의 모든 노드와 연결된 노드까지의 경로 변경 및 탐색

현재 S의 모든 요소와 연결된 노드까지의 길이를 새로 구한 경로와 비교하여 더 작은 값으로 변경해준다. 0번노드와 연결된 노드인 1,2번 노드의 경로 길이인 D[1,2]의 값은 무한대였으므로 새로 구한 경로인 4와 1로 변경해준다. 모든 새로운 경로의 길이를 구한 다음, 아직 탐색이 완료되지 않은 노드들 중에서 경로 길이가 제일 짧은 노드를 선택하여 탐색한다. 아래와 같은 경우, 탐색이 완료되지 않은 노드인 1,2,3 번 노드들 중에서 2번 노드의 경로가 제일 짧으므로 2번 노트를 탐색하여 집합 S에 추가해준다.

3. 모든 노드가 S에 추가될 때까지 반복

모든 노드가 S에 추가될 때까지 위와 같은 과정을 반복하면 시작노드로부터 모든 노드까지의 경로 길이를 구할 수 있다.