728x90
1. 벨만 포드
: 그래프 상의 한 정점으로부터 다른 모든 정점들까지의 최단 경로를 구하는 알고리즘
- single-source 최단경로 알고리즘
- 가중치가 음수인 경우도 적용 가능
- 가중치가 사이클을 이루는 경우 불가능
- 시간 복잡도 O(nm)
(최악의 경우 최대 n개의 정점, n-1개의 간선)
- 동작과정
- 가장 가까운 노드를 탐색해 한 단계 거칠 때마다 최단 거리를 확정해 나감.
- (n-1)번 반복해 모든 노드 간의 최단 거리를 완화해 나감.
s에서 u까지의 최단 경로가 다음과 같다고 가정하자.
- 처음에는 모두 upper[] 상태
- 시작노드인 s는 upper[s] = dist [s] = 0 이다.
- 모든 간선을 탐색해 relaxation 과정을 반복한다.
- upper[a] <= upper[s] + w(s,a)가 성립하고, upper[s] = dist[s] = 0이므로 upper[a] <= w(s,a)이다.
- 여기에서 w(s,a)는 s에서 a로 가는 최단 경로여야 한다. 최단 경로가 아니라면, 처음에 가정한 s에서 u까지의 최단 경로에 모순이 생기기 때문이다.
이 과정을 (n-1)번 반복하면 모든 노드에 대해 최단 경로를 확정할 수 있다.
- relaxation 과정
RELAX(u, v, w):
if dist[v] > dist[u] + w[u, v]
then dist[v] <- dist[u] + w(u,v)
upper[v] <- u
<벨만 포드 알고리즘 코드>
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
edges = []
inf = 1e9
dist = [inf] * (n + 1)
dist[1] = 0 # 1번 노드에서 출발
for _ in range(m):
a, b, c = map(int, input().split())
edges.append((a, b, c))
# 음의 가중치가 존재하기 때문에 다익스트라 사용 불가.
def bellman_ford():
# 모든 간선을 n-1번 순회하면 음의 순환이 없다는 가정하에
# 모든 노드까지의 최단 거리를 구할 수 있다.
# 그러니 총 n번을 순회하고 마지막 n번에 값이 바뀐다면
# 가중치가 음수인 간선들이 무한 루프를 도는 것이다.
for i in range(n):
for a, b, c in edges:
# 무한이 아니고, 현재 노드를 거쳐 가는 것이 더 비용이 적으면 갱신
if dist[a] != inf and dist[b] > dist[a] + c:
if i == n - 1: # n번째에 갱신된 경우
return False
dist[b] = dist[a] + c
return True
if not bellman_ford():
print(-1)
else:
for x in dist[2:]:
print(x) if x != inf else print(-1)
2. 다익스트라
: 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘
- single-source 최단경로 알고리즘
- 우선 순위 큐 사용- 음수 가중치에는 사용 불가
- 시간 복잡도 O(nlogn)
- 동작 과정
- 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택해 한 단계씩 최단 거리를 구해나감.
<수도 코드>
function Dijkstra(Graph, Source):
dist[source] ← 0 // 소스와 소스 사이의 거리 초기화 --출발지와 출발지의 거리는 당연히 0--
prev[source] ← undefined // 출발지 이전의 최적 경로 추적은 없으므로 Undefined
create vertex set Q //노드들의 집합 Q(방문되지 않은 노드들의 집합) 생성 시작
for each vertex v in Graph: // Graph안에 있는 모든 노드들의 초기화
if v ≠ source: // V 노드가 출발지가 아닐 경우(출발지를 제외한 모든 노드!)
dist[v] ← INFINITY // 소스와 V노드 사이에 알려지지 않은 거리 --얼마나 먼지 모르니까-- = 무한값 ( 모든 노드들을 초기화하는 값)
prev[v] ← UNDEFINED // V노드의 최적경로 추적 초기화
add v to Q // Graph에 존재하고 방금 전 초기화된 V 노드를 Q(방문되지 않은 노드들의 집합)에 추가
//요약하자면, Graph에 존재하는 모든 노드들을 초기화한 뒤, Q에 추가함.
while Q is not empty: // Q 집합이 공집합 아닐 경우, 루프 안으로!
u ← vertex in Q with min dist[u] // 첫번째 반복에서는 dist[source]=0이 선택됨. 즉, u=source에서 시작
remove u from Q // U 노드를 방문한 것이므로 Q집합에서 제거
for each neighbor v of u: // U의 이웃노드들과의 거리 측정
alt ← dist[u] + length(u, v) // 출발지 노드 부터 계산된 U노드까지의 거리 + V에서 U의 이웃노드까지의 거리
//= source to U + V to U = source to U
if alt < dist[v]: // 방금 V노드까지 계산한 거리(alt)가 이전에 V노드까지 계산된 거리(dist[v])보다 빠른 또는 가까운 경우
dist[v] ← alt // V에 기록된 소스부터 V까지의 최단거리를 방금 V노드까지 계산한 거리로 바꿈
prev[v] ← u // 제일 가까운 노드는 지금 방문하고 있는 노드(U)로 바꿈
return dist[], prev[] //계산된 거리값과 목적지를 리턴
3. 플로이드 워셜 알고리즘
: 그래프 내에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘
- All fairs 최단 경로 알고리즘
- 동적 계획법 기반
- 2차원 배열
- 시간 복잡도 O(n^2)
참고
728x90
'CS > 자료구조' 카테고리의 다른 글
| [자료구조] 전화번호부 v1.0 (0) | 2022.09.18 |
|---|---|
| [자료구조] 문자열 읽고 쓰기 (0) | 2022.09.18 |
| [자료구조] Graph(그래프) - DAG (0) | 2022.06.02 |
| [자료구조] Graph(그래프) - 깊이우선순회 DFS (0) | 2022.06.02 |
| [자료구조] Graph(그래프) - 너비우선순회 BFS (0) | 2022.05.24 |
