[ALGORITHM] 최단경로(다익스트라, 플로이드와샬)

최단경로

노드간 이동할 때 가중치가 1인 경우에는 BFS(너비 우선 탐색)를 이용해 쉽게 최단거리를 구할 수 있었습니다. 그렇다면 가중치가 1이 아닌 경우에는 어떻게 풀어야 할까요? 이때는 BFS가 아닌 Dijkstra(다익스트라)와 Floyd-warshall(플로이드-와샬) 탐색 기법을 이용해 문제를 풀 수 있습니다. 가중치가 음수일 경우 이용할 수 있는 Bellman Ford(벨만 포드) 기법도 있지만 이 글에서는 우선 다익스트라와 플로이드-와샬에 대해서만 배워 보겠습니다.

 

다익스트라(Dijkstra)

다익스트라 알고리즘은 에츠허르 다익스트라가 고안한 알고리즘으로 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단거리를 구해주는 알고리즘입니다. 다익스트라의 기본 개념은 출발 지점에서 부터 방문하지 않은 인접노드들 중 가장 가까운 지점들을 방문하며 특정 지점까지의 최단 거리를 계속해서 갱신해 준다는 것입니다. 아래 예시를 보면서 좀 더 자세히 알아보겠습니다.

1. 출발지를 s로 정하고, 다음과 같이 표시한다.
      (s,    t,     x,     y,     z  순)
거리 = [0,    inf,   inf,   inf,   inf]
방문 = [True, False, False, False, False]

2. 갈 수 있는 노드들의 최소거리를 측정한다.
s->t: 10
s->y: 5
      (s,    t,     x,     y,     z  순)
거리 = [0,    10,    inf,   5,     inf]
방문 = [True, False, False, False, False]

3. 방문 안한 녀석들 중 가장 가까운 녀석인 y를 방문하고, 최소거리를 측정한다.
y->t: 3
y->x: 9
y->z: 2
      (s,    t,     x,     y,    z  순)
거리 = [0,    8,     14,    5,    7]
방문 = [True, False, False, True, False]

4. 방문 안한 녀석들 중 가장 가까운 녀석인 z를 방문하고, 최소거리를 측정한다.
z->x: 6
      (s,    t,     x,     y,    z  순)
거리 = [0,    8,     13,    5,    7]
방문 = [True, False, False, True, True]

5. 방문 안한 녀석들 중 가장 가까운 녀석인 t를 방문하고, 최소거리를 측정한다.
t->x: 1
t->y: 2
      (s,    t,     x,    y,    z  순)
거리 = [0,    8,     9,    5,    7]
방문 = [True, True, False, True, True]

6. 방문 안한 녀석들 중 가장 가까운 녀석인 x를 방문하고, 최소거리를 측정한다.
x->z: 4
      (s,    t,     x,    y,    z  순)
거리 = [0,    8,     9,    5,    7]
방문 = [True, True, True, True, True]

7. 방문 안한 노드가 없으므로 끝낸다.
      (s,    t,     x,    y,    z  순)
거리 = [0,    8,     9,    5,    7]
방문 = [True, True, True, True, True 

다익스트라 구현방법

처음 다익스트라를 구현했을때는 O(V^2)의 시간복잡도를 가지고 있었습니다. 이 방법으로 구현해도 다익스트라 알고리즘을 풀수 있지만 입력되는 노드의 수가 많아지면 시간초과가 발생하는 문제점이 있어서 여기서는 개선된 방법인 우선순위 큐를 이용한 방법으로 구현해보겠습니다.

6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2

- 먼저 가장 첫줄에 노드의 개수(n)와 간선의 개수(m)이 주어집니다.

- 두 번째 줄에 시작 노드의 번호가 주어집니다.

- 세 번째 줄부터 m개의 간선의 정보(시작노드, 끝 노드, 가중치)가 주어집니다.

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

for _ in range(m):
        a, b, c = map(int, input().split())
        graph[a].append((b, c))

import heapq

INF = int(1e9)

def dijkstra_pq(graph, start):
    N = len(graph)
    dist = [INF] * N

    q = []
    heapq.heappush(q, (0, start))
    dist[start] = 0

    while q:
        acc, cur = heapq.heappop(q)

        if dist[cur] < acc:
            continue

        for adj, d in graph[cur]:
            cost = acc + d
            if cost < dist[adj]:
                dist[adj] = cost
                heapq.heappush(q, (cost, adj))

    return dist

 

플로이드 와샬(Floyd-warshall)

다익스트라 알고리즘이 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단거리를 구해주는 알고리즘이었다면 플로이드 와샬 알고리즘은 모든 정점에서 자기 자신을 제외한 모든 정점까지의 최단거리를 구해주는 알고리즘입니다. 

 

- 자기 자신으로 가는 가중치 = 0

- 연결되어 있지 않은 노드 = ∞

 

플로이드 와샬 구현방법

- 먼저 가장 첫줄에 노드의 개수(n)와 간선의 개수(m)이 주어집니다.

- 두 번째 줄에 시작 노드의 번호가 주어집니다.

- 세 번째 줄부터 m개의 간선의 정보(시작노드, 끝 노드, 가중치)가 주어집니다.

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

for _ in range(m):
        a, b, c = map(int, input().split())
        graph[a].append((b, c))

INF = int(1e9)

def floyd_warshall(graph):
    N = len(graph)
    dist = [[INF] * N for _ in range(N)]

    for idx in range(1, N):
        dist[idx][idx] = 0

    for start, adjs in graph.items():
        for adj, d in adjs:
            if dist[start][adj] > d:
                dist[start][adj] = d 

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

    return dist