1. 다익스트라
그래프 상에서 특정 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘이다.
현재 계산된 경로에서 최선의 경로를 찾기 때문에, 그리디의 성격을 띄고 있다.
따라서 음의 가중치가 존재한다면 다익스트라를 사용해서 풀 수 없을수도 있다.
그 이유는 다익스트라는 최단거리를 그리디로 찾는데, 음의 가중치가 있으면 이미 처리한 경로보다 더 짧은 경로가 나중에 등장할 수 있다.
만약 음의 가중치가 포함된다면, 플로이드 워셜이나 벨만 포드 알고리즘을 사용하여야 한다.
import heapq
def dijkstra(start):
q = []
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue
for i in graph[now]:
if dist+i[1] < distance[i[0]]:
distance[i[0]] = dist+i[1]
heapq.heappush(q, (dist+i[1], i[0]))2. 벨만 포드
다익스트라를 보완한 알고리즘
그래프 상에서 특정 한 노드에서 다른 모든 노드까지의 최단거리를 구한다.
음의 가중치가 존재했을 때 벨만포드를 사용
그래프에 N개의 노드가 있다면, 출발 노드에서 다른 모든 노드로 가는 최단 경로는 최대 N-1개의 간선을 사용할 수 있다.
따라서 N-1번의 반복을 수행하여 모든 노드에 대한 최단 경로를 찾을 수 있다.
마지막 반복 때 사이클 판별이 가능하다.
N-1번의 반복을 수행하고 N번째 iteration때도 최단 경로가 업데이트 된다면 이는 음수 사이클이 존재한다는 것을 의미한다.
다익스트라와 다른 점은 매번 모든 간선을 확인한다는 점
def bellman_ford(start):
distance[start] = 0
for i in range(N):
for j in range(M):
current_node, next_node, cost = edges[j]
if distance[current_node] != INF and distance[next_node] > distance[current_node] + cost:
distance[next_node] = distance[current_node] + cost
if i == N-1:
return True
return False
3. 플로이드 워셜
모든 노드 간의 최단거리를 구할 때 사용.
음의 가중치는 허용하나, 음의 사이클이 존재할 경우 당연하게도 최단거리를 구할 수 없다.
시간복잡도 O(N^3)
def floyd_warshall():
dist = [[INF for _ in range(n)] for _ in range(n)]
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return distShare article
