최단 경로 다익스트라/플로이드 워셜

다익스트라

특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 기본적으로 그리디 알고리즘으로 분류된다. 해당 알고리즘 코드는 꼭 숙지하고 외워두도록 하자!

참고로 해당 소스코드의 시간 복잡도는 O(ElogV)이다.

import heapq
INF = 1e9

n, m = map(int, input().split())
start = int(intput()) # 시작 노드
graph = [[] for i in range(n+1))]
distance = [INF] * (n+1)

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    
def dijkstra(start):
    q = []
    heapq.heappush((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]))

플로이드 워셜

모든 지점에서 다른 모든 지점까지의 최단경로를 모두 구해야 하는 경우 사용할 수 있는 알고리즘이다. 플로이드 워셜 알고리즘은 다이나믹 프로그래밍으로 분류된다. 시간 복잡도는 O(N^3)이다.

INF = 1e9

n, m = map(int, input().split())
graph = [[INF] * (n+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, n+1):
        if a == b:
            graph[a][b] = 0

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c
    
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][b], graph[a][k] + graph[k][b])