[python] 최단경로 정리

다익스트라 알고리즘

-한 지점에서 다른 특정 지점까지의 최단경로 

import heapq

start = int(input()) # 시작할 노드 설정
graph = [[] for i in range(n+1)] # n == 노드의 개수
distance = [1e9]*(n+1)

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]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(start)
print(distnace[destination]) # 구하고자하는 목적지까지의 최소비용

 

플로이드 워셜

-모든 지점에서 다른 모든지점까지의 최단경로

 

graph 초기설정:

graph = [[INF]*(n+1) for _ in range(n+1)] # 비용 저장하는 그래프

graph[i][j]

if i == j: graph[i][j] = 0

for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][k]+graph[k][b])