최단 경로 알고리즘(다익스트라, 벨만-포드, 플로이드-와셜)

대표적인 그래프 내 특정 정점에서 갈 수 있는 모든 정점들까지의 최단 경로를 구하는 알고리즘들로는 다익스트라, 벨만-포드, 플로이드-와셜 알고리즘이 있다.
이 세가지 모두 Optimal substructure 의 개념을 이용하여 최단 경로를 찾는데 이는 중간의 정점들이 각각 최단이 된다면 이를 모두 이은 경로 또한 최단이 된다는 개념이다.
따라서 한 정점에서 다른 정점까지 가는 도중 다른 정점을 거쳐 지나가는 것이 더 짧은지 확인하고 값을 갱신하여 최단 거리를 찾는다는 공통점이 있지만 알고리즘마다 약간의 차이가 있다.
자세한 내용은 순서대로 각 알고리즘에 대해 작성해보도록하겠다.

다익스트라 알고리즘

다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점까지의 최단 경로 를 구하는 알고리즘으로 큰 특징 중 하나는 간선의 가중치가 음수인 것이 하나라도 있다면 사용할 수 가 없다는 점 이다.
현실 세계에서는 음의 간선이 존재하지 않기에 실제로도 사용이 많이 되는 알고리즘이고 가능한 적은 비용으로 가장 빠르게 해답에 도달하는 경로를 찾아내는 대부분의 문제에 응용된다.

최단 거리는 여러개의 최단 거리로 이뤄져있기에 다익스트라 알고리즘은 동적 프로그래밍에 포함이 된다.
이는 최단 거리를 구할 때 그 전까지 구했던 최단 거리 정보를 그대로 사용한다는 것이다.

알고리즘 순서는 다음과 같다.

출발 노드를 설정한다.
출발 노드를 기준으로 각 노드의 최소 비용을 저장한다. (프로그래밍시에는 이차원 배열로 저장한다.)
방문하지 않는 노드들 중에서 가장 비용이 적은 노드를 선택한다.
해당 노드를 거쳐 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신한다.
위 과정을 반복한다.

프로그래밍시 우선순위 큐를 이용하여 문제를 해결한다.
다음은 파이썬으로 작성된 다익스트라 알고리즘 기본 코드(백준 1753 최단경로 문제)이다.

import sys
import heapq
INF = int(1e9)

v, e = map(int, sys.stdin.readline().split())
k = int(sys.stdin.readline())
# graph에 노드 정보 담기
graph = [[] for i in range(v + 1)]
for _ in range(e):
    u, vv, w = map(int,sys.stdin.readline().split())
    graph[u].append((vv, w))

def dijkstra(k):
    distance = [INF] * (v + 1)
    q = []
    # 시작 노드로 가기 위한 최단 경로를 0으로 설정하여 큐에 삽입
    heapq.heappush(q, (0, k))
    distance[k] = 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]))

    return distance


answer = dijkstra(k)

for i in range(1, v+1):
    if answer[i] == INF:
        print("INF")
    else:
        print(answer[i])

벨만-포드 알고리즘

벨만-포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 하나의 정점에서 다른 모든 정점까지의 최단 경로 를 구하는 알고리즘이다.
다익스트라보다 시간은 오래걸리지만 다익스트라와 다르게 간선의 가중치가 음수인 경우에도 가능하지만 이가 사이클을 이루고 있는 경우에는 불가하다.
따라서 최단경로는 순환을 포함해서는 안되므로 경로의 최대 길이는 |V|-1이다.
(간선이 음수든 양수든 간선 길이의 합이 적은 것이 최단 거리이다.)
벨만포드 수도코드는 다음과 같다.

(RELAX 는 해당 정점에 대해서 더 낮은 가중치로 도달할 수 있는 경우, 그 값을 갱신해주는 것을 말한다)

플로이드-와셜 알고리즘

플로이드-와셜 알고리즘은 모든 최단 경로를 다 구하는 알고리즘이다.
다익스트라와 다르게 간선의 가중치가 음수인 경우도 사용이 가능하나 벨만-포드와 마찬가지로 이가 사이클을 이뤄서는 안된다.
플로이드-와셜에서는 모든 경로에 대한 비용을 저장하는 테이블과 각 정점까지 가기 직전의 정점한 테이블, 총 2개의 테이블을 사용한다. 이 두 테이블 모두 처음에는 인접 리스트에 대한 내용만 들어가게 되고 경로를 추가할 때마다 테이블이 갱신된다.

참고

https://m.blog.naver.com/ndb796/221234424646
https://ssungkang.tistory.com/entry/Algorithm-%EB%B2%A8%EB%A7%8C%ED%8F%AC%EB%93%9CBellman-Ford-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://hsp1116.tistory.com/45

다익스트라 알고리즘

벨만-포드 알고리즘

플로이드-와셜 알고리즘

참고

Share this post