🌷 다익스트라

최단경로, 최소비용 탐색 알고리즘

한 노드에서 특정 노드까지의 최단거리

음의 간선이 존재하지 않아야 함. 방향 유무 무관

알고리즘

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])

정리