알고리즘 - 20 그래프 알고리즘 (최단 경로)

최단 경로 shortest path

최단 경로 조건

- 간선 가중치가 있는 유향 그래프

- 무향 그래프는 각 간선에 대해 유향 간선이 있는 유향 그래프로 생각할 수 있음

 -> 무향 간선 [u, v]는 유향 간선 [u,v]와 [v, u]가 존재한다고 가정하면 됨

 

두 정점 사이의 최단 경로

- 두 정점 사이의 경로들 중 간선의 가중치 합이 최소인 경로

- 간선 가중치의 합이 음인 싸이클이 있으면 문제가 정의되지 않음

 

단일 시작점 최단 경로

- 단일 시작점으로부터 각 정점에 이르는 최단 경로를 구함

- 다익스트라 알고리즘 : 음의 가중치를 허용하지 않는 최단경로

- 벨만 포드 알고리즘 : 음의 가중치를 허용하는 최단 경로

- 싸이클이 없는 그래프의 최단 경로

 

 

모든 쌍 최단 경로

- 모든 정점쌍 사이의 최단 경로를 모두 구함

- 플로이드-워샬 알고리즘

 

 

다익스트라 알고리즘

다익스트라 알고리즘 개요

- 음의 가중치가 없는 그래프에서 한 노드에서 다른 모든노드까지의 최단 거리를 구하는 알고리즘

- 에츠허르 데이크스타라 라는 네덜란드 출신의 컴퓨터 과학자에 의해 고안됨

 

다익스트라 알고리즘 예제

1. 시작정점 r만 최단거리 0으로 초기화하고 다른 정점들의 최단거리는 모두 무한대로 초기화함

 

 

2. 정점 r을 집합 S의 첫 번째 워소로 포함 시킴

3. 정점 r에 연결된 집합 S 바깥의 정점들을 살핌

 

4. 정점 r에서 바깥 정점들에 이르는 거리를 각 정점에 기록함

- 집합 S는 정점 r만으로 구성되어있음

- r에서 정점에 이르는 거리는 각 '8', ''9', '11'임

- 정점에서 기록돈 값은 시작 정점 r에서 해당 정점에 이르는 현재까지의 최단 거리임

- 연결된 세 정점 각각 '8', '9', '11'의 최단 거리값을 가짐

- 나머지 정점들은 모두 무한대의 최단거리 값을 가짐

5. 계산되어 있는 최단거리가 가장 짧은 정점을 집합 S에 포함시킴

- 집합 S의 바깥 정점들 중 최단 거리값이 가장 낮은 것은 '8'임

- 가장 짧은 정점 '8'을 집합 S에 포함시키고 나니 한 정점의 최단 거리 값이 무한대에서 '18'로 바뀜

- 집합 S 바깥 정점들 중 최단거리 값이 가장 낮은 것은 '9'임

 

 

6. 연결 비용이 '9'인 정점을 집합 S에 포함시킴

- 최단거리 '18'이던 정점의 최단거리가 '10'으로 바뀜

 -> 정점의 최단 거리가 무한대가 아닌 수에서 바뀌는 이유 : 기존 경로보다 더 짧은 경로가 발견된 경우

 -> 정점의 최단 거리는 여러번 바뀔 수 있음

- 나머지 정점들 중 최단 거리 값이 가장 낮은 것은 '10'임

7. 연결 비용이 '10'인 정점을 집합 S에 포함시킴

- 가장 짧은 정점 '10'을 집합 S에 포함시키고 나니 한 정점의 최단거리값이 무한대에서 '12'로 바뀜

 

8. 최단거리 '11'인 정점이 집합 S에 추가됨

- 두 정점의 최단 거리 값이 무한대에서 '19'로 바뀜

9. 최단 거리 '12'인 정점이 집합 S에 추가됨

- 한 정점의 최단 거리 값이 '19'에서 '16'으로 바뀜

10. 최단거리 '16'인 정점이 집합 S에 추가됨

11. 마지막 정점이 '19'의 최단거리로 집합 S에 추가되면서 알고리즘이 끝남

 

 

다익스트라 알고리즘이 작동하지 않는 예제

ex1. 음의 가중치가 문제를 일으키는 경우

- 간선 하나를 6에서 -15로 바꿈

-> (b)처럼 최단거리 -6으로 바뀌어야 함.

 

 

벨만 포드 알고리즘

벨만 포드 알고리즘 개요

- 입력 그래프 G(V, E)에서 간선의 가중치가 음의 값을 허용햐는 임의의 실수인 경우 최단 경로 알고리즘

- 간선을 최대 1개를 사용하는 최단 경로, 간선을 최대 2개 사용하는 최단경로, ... 이러한 식으로 간선을 최대 n - 1개 사용하는 최단 경로까지 구함

 

벨만 포드 알고리즘 예제

1. 시작 정점 r의 최단거리만 0으로 세팅하고 나머지는 모두 무한대로 초기화

2. 모든 간선을 한번씩 살피면서 해당 간선으로 인해 앞으로 설정한 최단 거리가 더 짧아질 수 있는지 살펴봄

- 시작 정점에 연결된 세 정점만 변동이 생김

- 이들 최단 거리가 무한대에서 8, 9, 11로 각각 바뀜

 

3. 모든 간선을 다시 한번씩 살피면서 해당 간선으로 인해 앞에서 설정된 최단 거리가 더 짧아질 수 있는지 봄

- 앞에서 세 개의 정점에 변동이 생겼으므로 이번에는 이들로부터 연결된 정점들에 변동이 생길 수 있음

- 이들의 최단거리가 8, 무한대, 무한대, 무한대에서 -6, 10, 19, 19로 각각바뀜

- 이중 -6으로 바뀐 정점은 바로 전단계인 (b)에서도 바뀌었는데 최단 거리 9인 정점으로부터 연결되어 있어 다시 -6으로 바뀜

 

4. for 루프마다 모든 간선을 한 번씩 살피면서 해당 간선으로 인한 최단거리 변동 여부를 살펴봄

6. 마지막 for 루프 (i=7)에서는 아무런 변동이 일어나지 않음

- 시작 정점에서 7개의 간선을 사용하는 최단경로는 없다는 뜻