Graph (Shortest path problem)
1. Single-Source Shortest Path Problem
Bellman-Ford Algorithm
- 음수의 간선을 포함하는 그래프에서의 최단거리 알고리즘.
- Relaxation : u를 통해서 v로 가는것이 기존의 d 최단거리보다 짧은 경우, d[v]와 π[v]를 업데이트.
RELAX (u,v,w)
if d[v] > d[u] + w(u,v) :
then d[v] <- d[u] + w(u,v)
π[v] <- u
BellmanFord(Graph, source):
// Graph: the graph where Graph.vertices represent the vertices and Graph.edges represent the edges
// source: the source vertex from which to calculate the distances
// Step 1: Initialize the distances from the source to all vertices as infinite and distance to the source itself as 0
distance[] = array of size equal to number of vertices, initially filled with infinity
distance[source] = 0
// O(V)
// Step 2: Relax all edges |V| - 1 times (V is the number of vertices)
for i from 1 to size(Graph.vertices) - 1:
for each edge (u, v) in Graph.edges:
if distance[u] + weight(u, v) < distance[v]:
distance[v] = distance[u] + weight(u, v)
// O(VE)
// Step 3: Check for negative-weight cycles
for each edge (u, v) in Graph.edges:
if distance[u] + weight(u, v) < distance[v]:
print("Graph contains a negative-weight cycle")
return
// O(E)
// If the algorithm reaches here, then there are no negative weight cycles, and
// distance[] contains the shortest paths from the source
return distancestep1. source로부터 all vertices에 대한 거리를 초기화
step2. all edges를 relax한다. (Vertices-1 갯수만큼 반복)
step3. vertices-1 횟수만큼하고나서도 2번을 한번더 했을때 거리가 줄어드는 경우 negative cycle이 존재한다는것을 알 수 있다.
시간복잡도 : step2에서 모든 edge를 체크하는 과정을 vertex 갯수만큼 반복하므로 O(|V||E|).
Dijkstra’s Algorithm
- positive weight만 존재할때 가능한 방식. bellman-ford보다 빠름.
- positive weight cycle을 다룰 수 있다.
- priority queue를 사용한다.
- 매 step에서 현재 set에서 연결가능한 가장 가까운 vertex를 추가한다.
- Bellman-Ford는 모든 edge를 relaxation 거쳤지만 여기서는 “추가된 vertex”에서만 relaxation한다.
Dijkstra(Graph, source):
// Graph는 노드들의 집합 V와, 각 노드 쌍 사이의 거리를 나타내는 간선들의 집합 E를 가진 구조체이다.
// source는 시작 노드의 번호이다.
create vertex set Q // 모든 노드들을 저장할 집합
for each vertex v in Graph.V: // 초기화
dist[v] = INFINITY // 소스에서 v까지의 알려진 최단 거리는 무한대로 설정
prev[v] = UNDEFINED // v의 이전 노드는 아직 알려지지 않음
add v to Q // 모든 노드를 Q에 추가
dist[source] = 0 // 소스에서 소스까지의 거리는 0
while Q is not empty:
u = vertex in Q with min dist[u] // Q에서 dist[u]가 최소인 노드 u를 선택
remove u from Q
for each neighbor v of u: // u의 모든 인접 노드 v에 대해
alt = dist[u] + length(u, v)
if alt < dist[v]: // u를 경유하는 것이 v까지의 현재 알려진 최단 거리보다 짧은 경우
dist[v] = alt // dist[v]를 갱신
prev[v] = u // v의 이전 노드를 u로 설정
return dist[], prev[]시간복잡도는 우선순위큐를 사용하지않으면, O(V²)
우선순위큐를 사용하면, 삽입에 각 edge별로 O(logV)씩 소요되어서 총 O(ElogV).
큐에서 제거하는 작업에는 Vertex 갯수만큼 O(logV)씩 소요되어서 총 O(VlogV).
합쳐서 총 O((E+V)logV)가 걸린다.
2. All-Pairs Shortest Path Problem
w/o negative weight edge / Dijkstra’s algorithm
- based on a linear array : O(V³+VE) = O(V³)
- based on a min-heap : O(VElogV)
- based on a fibonacci heap : O(V²logV +VE)
w/ negative weight edge / Bellman-Ford algorithm
- O(V²E)= O(V⁴)
Floyd-Warshall Algorithm
Dynamic programming을 적용하여 현재 위치에서 목적지까지 갈때 ‘다른 경유지를 거치는게 나은지’ 모두 확인하는 방법.
Dab = min (Dab, Dak + Dkb).
FloydWarshall(graph):
// graph는 정점 쌍 간의 가중치를 포함하는 2차원 배열로 표현된 그래프입니다.
// graph[i][j]는 정점 i에서 정점 j로 가는 간선의 가중치입니다.
// graph[i][i] = 0, 간선이 존재하지 않는 경우 graph[i][j] = ∞ (무한대).
n = graph의 정점 수
// dist 배열을 graph로 초기화합니다. 이 배열은 알고리즘 실행 후 최단 거리를 저장합니다.
dist = 배열 크기 [n][n]
for i from 0 to n-1:
for j from 0 to n-1:
dist[i][j] = graph[i][j]
// 모든 정점을 경유지로 하여 각 정점 쌍의 최단 거리를 계산합니다.
for k from 0 to n-1: // k는 경유지
for i from 0 to n-1: // i는 시작 정점
for j from 0 to n-1: // j는 도착 정점
// 경유지 k를 거쳐가는 경로가 더 짧은 경우, 거리를 업데이트합니다.
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist시간복잡도는 총 O(V³)이다. Negative weight edge가 있는 경우 Bellman-Ford를 모든 시작점에서 체크하는 것보다 ( O(V⁴) ) 빠르다.
