최단경로 알고리즘

최단 경로 알고리즘(길 찾기)은 가장 짧은 경로를 찾는 알고리즘으로, 많이 나오는

다익스트라 알고리즘, 플로이드 워셜 알고리즘, 벨만 포드 알고리즘 이렇게 3가지를 잘 알아두어야 한다. 

🙋 다익스트라 최단 경로 알고리즘

다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘이다. (즉, 출발 노드로부터 다른 모든 노드까지의 최단거리 구하기!)

이 알고리즘은 기본적으로 매번 가장 비용이 적은 노드를 선택해 반복하기에, 그리디 알고리즘으로 분류된다. 

다익스트라 알고리즘의 과정은 다음과 같다.

 

1. 출발 노드를 정하고, 최단거리 테이블을 초기화시켜준다.

(자기자신에 대한 노드는 0으로, 나머지는 무한으로 설정)

 

해당 예제에서는 노드번호가 1인 노드를 출발노드로 설정

최단 거리 테이블 : 각 노드에 대한 현재까지의 최단거리 정보를 가진 테이블

더 짧은 경로를 찾으면, 더 짧은 경로로 값을 갱신해준다. 

실제 소스코드에서 무한을 나타낼때는, int(1e9)로 표현한다. (혹은 987654321)

 

2. 1번 노드를 거쳐 다른 노드로 가는 비용을 계산해준다. (= 1번과 연결된 모든 노드를 확인해준다)

 

 

2. 방문하지 않은 노드 중, 최단거리가 가장 짧은 노드를 선택한다.

즉, 4번 노드를 선택하여 처리한다.

4번 노드 선택

4. 해당 노드를 지나 다른 노드로 가는 비용을 계산하여 최단거리테이블을 갱신한다.

5번 노드의 값을 갱신해준다. 

 

5. 3과 4의 과정을 반복해준다.

 

2번노드와 5번노드 모두 거리가 2로 같기에, 무엇을 먼저 선택하든 상관없지만 일반적으로 노드번호가 더 낮은 2를 먼저 선택한다.