최단경로, 최소비용 탐색 알고리즘
한 노드에서 특정 노드까지의 최단거리
음의 간선이 존재하지 않아야 함. 방향 유무 무관
heapq에 시작할 노드 와 0 을 넣어준다.(시작시엔 가중치가 없으므로 0)
while heapq:
heappop하여 현재 노드와 가중치를 가진다.
방문할 노드와 연결되어 있는 노드들에 방문하며 거리를 갱신한다
if (기존거리 > 현재가중치+방문할노드까지가중치 ):
heappush (방문할노드 ,현재가중치+방문할노드까지가중치)
- heappush할때 현재가중치+방문할노드까지가중치 하는 이유는 ?
방문할노드까지가중치는 두 노드 사이의 가중치이다. 하지만 시작노드부터 누적값을 가져야 하므로 현재가중치를 더한 값을 가지고 있어야 한다.
def dijkstra(s):
distance[s] = 0
heapq.heappush(hq, (0, s))
while hq:
now_w, now_node = heapq.heappop(hq)
for next_w, next_node in arr[now_node]:
if now_w + next_w < distance[next_node]:
distance[next_node] = now_w + next_w
heapq.heappush(hq, (next_w+now_w, next_node)) #next_w + now_w 이어야함!
그래프에서 가능한 모든 노드 간의 최단거리
음의 간선도 가능
다익스트라DP에서는 한노드를 시작점으로 정하고 그 노드에 대해 나머지 노드로 가는 최단경로를 구하는 것이기 때문에 distance 일차원 배열을 두었지만
플로이드 워셜은 모든노드→모든노드 이기때문에 이차원 배열을 그대로 이용하면 된다
즉, A → B의 최단경로를 구하려면 A,B 중간에 다른 노드를 거쳐서 가는 경우들과 비교해야한다.
v, e = map(int,input().split())
graph = [[int(1e9) for _ in range(v+1)] for _ in range(v+1)]
for _ in range(e):
a,b,c = map(int,input().split())
graph[a][b] = c
for k in range(1,v+1):
for a in range(1,v+1):
for b in range(1,v+1):
graph[a][b] = min(graph[a][b],graph[a][k]+graph[k][b])
정리
다익스트라 | 플로이드워셜 | |
---|---|---|
용도 | 한 정점 -> 특정 정점 최단거리 | 모든 정점 -> 모든 정점 최단거리 |
간선 | 음X, 방향 무관 | 음의 간선 가능 |
자료구조 | 힙큐 사용 | 이차원 배열 사용 |
시간복잡도 | O((V+E)logV) | O(n³) |