최단 거리 알고리즘

최단 거리 알고리즘을 정리해보자.

 

1. 다익스트라 알고리즘

- 하나의 node로부터 다른 모든 node까지의 최단거리를 계산 가능

- 음의 간선이 없는 경우에만 유효

- O(VlogV)

import heapq

def dijkstra(start):
    pq = []
    heapq.heappush(pq, (0, start))
    distance[start] = 0
    while pq:
        dist_u, u = heapq.heappop(pq)
        # node u가 이미 처리된 경우
        if distance[u] < dist_u:
            continue
        for 모든 u와 연결된 v에 대해:
            if distance[v] > dist_uv + dist_u:
              distance[v] = dist_uv + dist_u
              heapq.heappush(pq, (distance[v], v))

 

2. 플로이드-워셜 알고리즘

* 3개의 for문의 의미를 이해해둘 필요가 있다.

* 2번째, 3번째 for문: "모든 node(a->b) 쌍간의 거리를 갱신한다"

* 1번째 for문: k가 a->k->b의 중간다리 역할을 한다. 여기서 핵심은 중간다리로 거리를 갱신하는 행위를 n번한다는 것인데, 이는 a->b로 가는 최단거리를 갱신함에 있어서 1회 경유 path, 2회 경유 path, 3회 경유, ..., n-1회 경유하는 path 들이 최단거리인지 체크하면서 완전 탐색한다는 것이다.

- 모든 node 간의 최단 거리를 계산 가능

- O(V^^3)

graph = [[INF] * (n + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    graph[i][i] = 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][b], graph[a][k]+graph[k][b])

 

3. Bellman-Ford 알고리즘

- 음의 간선이 있는 경우에도 사용 가능

- 음의 cycle이 존재하는 경우에도 사용 가능

- 모든 간선에 대해 relaxation을 N번 반복하므로, O(VE)

def bf(dist_list, start):
    dist_list[start] = 0
    for i in range(n):
        for edge in edges:
            a = edge[0]
            b = edge[1]
            c = edge[2]
            if dist_list[a] != INF and dist_list[b] > dist_list[a] + c:
                dist_list[b] = dist_list[a] + c
                if i == n-1:
                    return True
return False

 

4. SPFA (Shortest Path Faster Algorithm)

- Bellman-Ford 알고리즘의 개선 버전

- Relaxation된 정점을 queue에 추가하는데, 이 때 추가하는 정점이 queue에 이미 존재하는지 여부를 따로 배열을 두어 관리한다. 

def spfa(dist_list, inqueue_list, start):
    q = []
    q.append(start)
    dist_list[start] = 0
    while q:
        now = q.popleft()
        inqueue_list[now] = False
        for next in graph[now]:
            cost = graph[now][next]
            if dist_list[next] != INF and dist_list[next] > dist_list[now] + cost:
                dist_list[next] = dist_list[now] + cost
                if not inqueue_list[next]:
                    q.append(next)
                    inqueue_list[next] = True