최단 경로 알고리즘

최단 경로 알고리즘은 목적지로 향하는 모든 경로 중 가중치의 합이 가장 작은 경로를 찾는 알고리즘이다.

알고갈 점

• 그래프 G(V,E)가 주어질 때 E는 가중치를 가진 유향 간선들의 집합이다.
  임의 경로는 연속된 간선들로 이뤄져 있다.

길이 : 이 경로를 구성하는 간선들의 가중치 합

• 최단 경로 문제에서 입력 그래프의 유형은 보통 2가지
  (1) 모든 간선의 가중치가 0이상인 경우
  (2) 가중치 중 음의 가중치가 있는 경우

(2)의 경우 음의 가중치는 허용하지만 가중치의 합이 음인 사이클은 허용하지 않는다.
음의 사이클이 있을 경우 무한으로 작은 값을 만들 수 있기 때문

다익스트라 알고리즘(Dijkstra)

입력 그래프가 (1)에 해당하는 경우 최단 경로를 찾는 알고리즘이다.
프림 알고리즘과 매우 흡사하다.
1. 시작 정점 r만 0으로 초기화 나머지 정점을 ∞로 놓는다
2. 정점 r을 집합 S에 포함시킨다.
3. 집합 S에서 인접한 정점들을 가중치의 비용으로 초기화한다.
4. 최단 거리가 가장 짧은 정점을 S에 포함 시킨다.
5. 3.,4.를 반복한다. 단, 값이 이미 있는 경우 기존 초기화된 값보다 낮을 때만 초기화한다.

벨만포드 알고리즘(Bellman-Ford)

입력 그래프가 (2)에 해당하는 경우 최단 경로를 찾는 알고리즘이다.
for문을 사용해 (정점의 개수 - 1)번의 간선을 거친 경로를 계산하며 값을 계속 초기화 시켜나가며 최단 거리를 찾는다.
1. 시작 정점 r의 최단 거리만 0으로 설정하고 나머지 정점을 ∞로 놓는다
2. 시작 정점 r에서 1개의 간선을 거치는 곳들의 가중치 값을 계산해 정점에 초기화한다. (1번째 반복)
3. 2.에서 초기화된 정점에서 1개의 간선을 거치는 곳들의 가중치 값을 계산해 정점에 초기화한다. 이때 해당 정점에 값이 이미 존재한다면 새로 계산한 값이 더 작을 때만 초기화한다.(2번째 반복)
4. 3.에서 반복한다. 이렇게 계속 반복해서 (정점의 개수 - 1)번의 간선까지 계산을 한다.

4번 과정을 반복하는 도중에 더이상 초기화할 정점이 없다면 해당 개수의 간선을 사용하는 최단 경로는 없다는 뜻이다.