다익스트라, 플로이드워셜 알고리즘

다익스트라 알고리즘

특정한 노드에서 출발하여 다른 노드로 가는 최단 경로를 구하는 알고리즘

• 그리디
• 음의 간선 없어야함

최단 경로 테이블을 갱신하는 방식

1. 리스트
2. 최소

코드

import heapq
N, M = map(int, input().split())
INF = int(1e9)
graph = [[] for _ in range(N + 1)]
distarnce = [INF] *(N + 1)

for _ in range(M):
	v, u, cost = map(int, input().split())
   	graph[v].append((u, cost))
 	start, end = map(int, input().split())

def dijkstra(start):
	que = []
	heapq.heappush(que, (0, start)) # cost, node
	
	while que:
		cost, node =  heapq.heappop(que)
		if distarnce[node] < cost:
			continue
        
       	for v in graph[node]:
			new_cost = cost + v[1]
           	if new_cost < distarnce[v[0]]:
				heapq.heappush(que, (new_cost, v[0]))
               	distarnce[v[0]] = new_cost

dijkstra(start)

플로이드 워셜 알고리즘

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우

• 2차원 리스트에 최단 거리 정보 저장
• 다이나믹 프로그래밍

점화식

\[D_{ab} = min(D_{ab}, D_{ak} + D_{kb})\]

코드

INF = int(1e9)
node_cnt = int(input())
edge_cnt = int(input())
graph = [[INF] * (node_cnt + 1) for _ in range(node_cnt + 1) ]
 
for x in range(1, node_cnt + 1):
	for y in range(1, node_cnt + 1):
       	if x == y:
			graph[x][y] = 0           

for _ in range(edge_cnt):
	vertex, edge, cost = map(int, input().split())
   	graph[vertex][edge] = cost

for k in range(1, node_cnt + 1):
	for x in range(1, node_cnt + 1):
		for y in range(1, node_cnt + 1):
			graph[x][y] = min(graph[x][y], graph[x][k] + graph[k][y])

for x in range(1, node_cnt + 1):
	for y in range(1, node_cnt + 1):
		print(graph[x][y], end=' ')
	print()