1. 다익스트라 알고리즘
사용 조건
시작점이 있다.
간선의 가중치에 음수가 없다.
과정
먼저, 출발 정점을 설정하고 해당 정점의 거리를 0으로 설정합니다.
나머지 정점들의 거리를 무한대로 초기화 합니다.
아직 방문하지 않은 정점들 중에서 하나를 선택합니다. 이때, 출발 정점에서 가장 짧은 거리를 가진 정점을 선택합니다.
모든 정점에 방문할 때까지 세 번째 과정을 반복합니다.
예제
A가 출발 정점일 때, A에서 연결되는 간선의 정보를 우선 순위 큐(최단 거리 우선)에 넣습니다.
우선 순위 큐에서 원소를 하나 꺼낼 때, 가장 짧은 거리인 B로 가는 1이 나옵니다.
이제 B에서 연결되는 간선의 정보를 수정(거리 추가)하여, 그 정보를 우선 순위 큐에 넣습니다.
우선 순위 큐에서 원소를 하나 꺼내면, 가장 짧은 거리인 C로 가는 4가 나옵니다.
C에서 연결되는 간선의 정보를 수정하여, 우선 순위 큐에 넣습니다.
이제 우선 순위 큐에서 원소 하나를 꺼내면, C로 가는 5가 나옵니다.
하지만 C는 이미 방문한 정점이므로, 버리고 다시 꺼내면 D로 가는 5가 나옵니다.
D에서 연결되는 간선의 정보를 수정하여, 우선 순위 큐에 넣습니다.
우선 순위 큐에서 원소 하나를 꺼내면, D로 가는 6이 나옵니다.
하지만 D는 이미 방문한 정점이므로, 다시 꺼내면 E로 가는 8이 나옵니다.
우선 순위 큐가 텅 빌 때까지 탐색을 하고 끝납니다.
각 정점에는 최단 거리의 정보가 남게됩니다.
만약 정점에 무한대의 최단 거리 정보가 남아있다면 갈 수 없는 정점입니다.
코드
from heapq import heappop, heappush
# 인접 행렬로 거리 정보를 담음(-1은 갈 수 없음)
data = [
[-1, 1, 4, -1, -1],
[-1, -1, 4, 5, -1],
[-1, -1, -1, 1, -1],
[-1, -1, -1, -1, 3],
[-1, -1, -1, -1, -1]
]
# 거리 정보 초기화(출발 정점은 0, 나머지 무한대)
INF = 1e9
dis = [0, INF, INF, INF, INF]
# 우선 순위 큐 초기화
priority_queue = []
for vtx, weight in enumerate(data[0]):
# 출발 정점으로부터 갈 수 있는 간선 정보를 우선 순위 큐에 담음
if weight != -1:
heappush(priority_queue, (weight, vtx))
# 우선 순위 큐가 빌 때까지 반복
while priority_queue:
# 우선 순위 큐에서 하나를 꺼내면 최단 거리 정보가 나옴
w, v = heappop(priority_queue)
# 방문 했다면 버림
if dis[v] != INF:
continue
# 최단 경로 등록
dis[v] = w
# 해당 정점에서 연결된 간선의 정보를 우선 순위 큐에 담음
for nxt, nw in enumerate(data[v]):
if nw != -1:
heappush(priority_queue, (w+nw, nxt)) # 거리 정보는 수정해야 함.
print(dis)
# [0, 1, 4, 5, 8]시간복잡도
(우선순위 큐를 사용했을 때)
\(O(\:\)(간선의 개수)\(\:+\:\)(정점의 개수)\(\log\)(정점의 개수)\(\:)\)
장점
빠르다.
단점
가중치가 음수일 때는 사용할 수 없다.
https://ko.wikipedia.org/wiki/데이크스트라_알고리즘
데이크스트라 알고리즘 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서 데이크스트라 알고리즘(영어: Dijkstra algorithm) 또는 다익스트라 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의
ko.wikipedia.org
2. 벨만-포드 알고리즘
사용 조건
시작점이 있다.
간선의 가중치에 음수가 있다.
과정
그래프에서 한 정점은 임의의 정점으로 이동할 때, 최악의 경우에 모든 정점을 거쳐서 가게 됩니다.
다시 말하면, 최악의 경우에도 (모든 정점의 수 - 1)만큼만 이동하면 연결된 어떤 정점에도 도착할 수 있게 됩니다.
따라서, (모든 정점의 수 - 1)만큼 반복적으로 간선의 가중치를 완화하면 최단 거리를 구할 수 있습니다.
만약 한 번 더 반복했는데 간선이 완화된다면, 음의 사이클이 존재한다는 것을 의미합니다.
예제
초기 거리 정보는 출발 정점(A)는 0, 나머지는 무한대로 초기화 합니다.
1회차에서 B와 C의 거리 정보가 완화됩니다.
실제 코드가 동작할 때는 정점의 탐색 순서에 따라 값이 달라질 수 있으나, (모든 정점의 수 - 1)회차까지 반복하면 결국 같아집니다.
2회차에서 C, D, E의 거리 정보가 완화됩니다.
3회차에서 D의 거리 정보가 완화됩니다.
4회차에서 더 이상 완화되는 정보가 없습니다.
여기까지 최단 거리 탐색이 완료되었습니다.
만약 5회차까지 진행했는데 완화되는 거리 정보가 있을 경우, 음의 폐선이 존재한다는 것을 의미합니다.
코드
인접 행렬 사용
# 인접 행렬로 거리 정보를 담음
INF = 1e9
data = [
[INF, 6, 13, INF, INF],
[INF, INF, 5, 5, -3],
[INF, INF, INF, -2, -3],
[INF, -3, INF, INF, INF],
[INF, INF, INF, 6, INF]
]
# 거리 정보 초기화(출발 노드는 0, 나머지 무한대)
dis = [0, INF, INF, INF, INF]
for i in range(5): # 총 5회차 실시
# 모든 정점에서 간선의 가중치를 확인하여 완화
for j in range(5): # j 정점으로부터
for nxt, weight in enumerate(data[j]): # nxt 정점으로
if dis[nxt] > dis[j] + weight: # 더 짧은 경로가 존재한다면
dis[nxt] = dis[j] + weight # 간선 완화
if i == 4: # 5회차에서 일어난다면 음의 사이클 존재
print("음의 사이클이 존재합니다.")
exit()
print(dis)
# [0, 6, 11, 9, 3]
간선의 정보를 배열로 사용
# 간선의 정보(출발 정점, 도착 정점, 가중치)
edges = [
(0, 1, 6),
(0, 2, 13),
(1, 2, 5),
(1, 3, 5),
(1, 4, -3),
(2, 3, -2),
(2, 3, 3),
(3, 4, 6)
]
# 거리 정보 초기화(출발 노드는 0, 나머지 무한대)
INF = 1e9
dis = [0, INF, INF, INF, INF]
# 벨만-포드 알고리즘
for i in range(5): # 총 5회차 실시
# 모든 정점에서 간선의 가중치를 확인하여 완화
for u, v, weight in edges: # u정점에서 v정점으로
if dis[v] > dis[u] + weight: # 더 짧은 경로가 존재한다면
dis[v] = dis[u] + weight # 간선 완화
if i == 4: # 5회차에서 일어난다면 음의 사이클 존재
print("음의 사이클이 존재합니다.")
exit()
print(dis)
# [0, 6, 11, 9, 3]시간복잡도
\(O(\:\)(정점의 개수)\(\:\times\:\)(간선의 개수)\(\:)\)
장점
간선의 가중치에 음수가 있어도 사용할 수 있다.
음의 폐선(음수로 계속 작아지는 사이클)을 찾을 수 있다.
단점
속도가 느림
https://ko.wikipedia.org/wiki/벨먼-포드_알고리즘
벨먼-포드 알고리즘 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 벨먼-포드 알고리즘(영어: Bellman-Ford algorithm)은 가중 유향 그래프에서 최단 경로 문제를 푸는 알고리즘이다. 이때 변의 가중치는 음수일 수도 있다. 데이크스트
ko.wikipedia.org
3. 플로이드-워셜 알고리즘
사용 조건
모든 정점 간의 최단거리를 알고 싶다.
간선의 가중치에 음수가 있다.
대신, 음의 폐선(음수 사이클)은 없다.
과정
각 정점 사이의 거리를 2차원 배열로 초기화합니다.(자기 자신은 0, 간선이 없으면 무한대)
정점을 차례로 선택한 후, 해당 정점을 지나가는 경로와 바로 가는 경로의 거리를 비교합니다.
예를 들어, 선택한 정점이 2이면, (1 -> 2 -> 3) 과 (1 -> 3) 의 거리를 비교합니다.
더 짧은 경로로 거리 정보를 갱신하면서 모든 정점에서 반복합니다.
예제
| 출발 노드 \ 도착 노드 | A | B | C | D | E |
| A | 0 | 2 | -5 | 8 | ∞ |
| B | ∞ | 0 | 5 | ∞ | 1 |
| C | ∞ | ∞ | 0 | ∞ | 7 |
| D | ∞ | 4 | ∞ | 0 | ∞ |
| E | 2 | ∞ | ∞ | -5 | 0 |
초기 그래프 정보를 2차원 배열로 나타냅니다.
| 출발 노드 \ 도착 노드 | A | B | C | D | E |
| A | 0 | 2 | -5 | 8 | ∞ |
| B | ∞ | 0 | 5 | ∞ | 1 |
| C | ∞ | ∞ | 0 | ∞ | 7 |
| D | ∞ | 4 | ∞ | 0 | ∞ |
| E | 2 | ∞ | ∞ | -5 | 0 |
먼저 A를 중간에 경유하는 정점으로 설정하고, B에서 모든 정점을 비교합니다.
B에서 A로 가는 경로가 없으므로, 모두 직접 가는 경우밖에 없으므로 수정되는 정보는 없습니다.
| 출발 노드 \ 도착 노드 | A | B | C | D | E |
| A | 0 | 2 | -5 | 8 | ∞ |
| B | ∞ | 0 | 5 | ∞ | 1 |
| C | ∞ | ∞ | 0 | ∞ | 7 |
| D | ∞ | 4 | ∞ | 0 | ∞ |
| E | 2 | ∞ | ∞ | -5 | 0 |
C, D에서 출발하는 경우에도 A를 경유해서 가는 경로가 없으므로, 수정되지 않습니다.
| 출발 노드 \ 도착 노드 | A | B | C | D | E |
| A | 0 | 2 | -5 | 8 | ∞ |
| B | ∞ | 0 | 5 | ∞ | 1 |
| C | ∞ | ∞ | 0 | ∞ | 7 |
| D | ∞ | 4 | ∞ | 0 | ∞ |
| E | 2 | 4 | -3 | -5 | 0 |
E에서 출발하는 경우, B와 C로 갈 때 A를 경유해서 가는 것이 (직접 가는 경우가 없어서) 더 짧으므로 거리 정보를 수정합니다.
이렇게 A를 경유해서 가는 경우를 모든 정점에서 확인하였습니다.
앞에서 A를 경유하는 모든 경로를 탐색해서 (E -> B), (E -> C)로 가는 경로가 수정되었으므로, 그래프에도 반영하였습니다.
이번에는 B를 경유하는 모든 경로를 탐색합니다.
| 출발 노드 \ 도착 노드 | A | B | C | D | E |
| A | 0 | 2 | -5 | 8 | 3 |
| B | ∞ | 0 | 5 | ∞ | 1 |
| C | ∞ | ∞ | 0 | ∞ | 7 |
| D | ∞ | 4 | ∞ | 0 | 5 |
| E | 2 | 4 | -3 | -5 | 0 |
B를 경유하는 모든 경로를 탐색한 결과, (A -> E), (D -> E)로 가는 경로가 수정되었습니다.
그래프에도 반영된 모습입니다.
이제는 C를 경유하는 모든 경로를 탐색합니다.
| 출발 노드 \ 도착 노드 | A | B | C | D | E |
| A | 0 | 2 | -5 | 8 | 2 |
| B | ∞ | 0 | 5 | ∞ | 1 |
| C | ∞ | ∞ | 0 | ∞ | 7 |
| D | ∞ | 4 | ∞ | 0 | 5 |
| E | 2 | 4 | -3 | -5 | 0 |
결과의 모습입니다.
이제 D를 경유하는 모든 경로를 탐색합니다.
| 출발 노드 \ 도착 노드 | A | B | C | D | E |
| A | 0 | 2 | -5 | 8 | 2 |
| B | ∞ | 0 | 5 | ∞ | 1 |
| C | ∞ | ∞ | 0 | ∞ | 7 |
| D | ∞ | 4 | ∞ | 0 | 5 |
| E | 2 | -1 | -3 | -5 | 0 |
결과의 모습입니다.
이제 마지막으로 E를 경유하는 모든 경로를 탐색합니다.
| 출발 노드 \ 도착 노드 | A | B | C | D | E |
| A | 0 | 1 | -5 | -3 | 2 |
| B | 3 | 0 | -2 | -4 | 1 |
| C | 9 | 6 | 0 | 2 | 7 |
| D | 7 | 4 | 2 | 0 | 5 |
| E | 2 | -1 | -3 | -5 | 0 |
이렇게 모든 정점에서의 최단 경로 확인이 완료되었습니다.
코드
# 거리 정보(자기 자신은 0, 경로가 없으면 무한대)
INF = 1e9
dis = [
[0, 2, -5, 8, INF],
[INF, 0, 5, INF, 1],
[INF, INF, 0, INF, 7],
[INF, 4, INF, 0, INF],
[2, INF, INF, -5, 0]
]
for mid in range(5): # 경유 정점 mid
for start in range(5): # 시작 정점 start
for end in range(5): # 도착 정점 end
direct = dis[start][end]
transit = dis[start][mid] + dis[mid][end]
if direct > transit: # 경유해서 가는 경우가 직접 가는 경우보다 짧은 경우
dis[start][end] = transit
for line in dis:
print(line)
# [0, 1, -5, -3, 2]
# [3, 0, -2, -4, 1]
# [9, 6, 0, 2, 7]
# [7, 4, 2, 0, 5]
# [2, -1, -3, -5, 0]시간복잡도
\(O(\:\)(정점의 개수)\(^{3}\)\(\:)\)
장점
모든 정점 간의 최단거리를 확인할 수 있다.
간선의 가중치에 음수가 있어도 확인할 수 있다.(단, 음의 폐선은 없어야 한다.)
단점
시간 복잡도가 \(O(n^3)\)으로 정점의 개수가 많아질수록 시간이 급격히 오래 걸린다.
음의 폐선이 있으면 정상적으로 작동하지 않는다.
https://ko.wikipedia.org/wiki/플로이드-워셜_알고리즘
플로이드-워셜 알고리즘 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고
ko.wikipedia.org
