최단경로 알고리즘 (Dijkstra, Bellman-Ford, Floyd-Warshall)

알고리즘 문제를 풀다보면 자주 나오는 유형이 바로 최단경로(Shortest Path) 구하기 문제이다.

이 때 대표적으로 쓰이는 다익스트라(Dijkstra), 벨만-포드(Bellman-Ford), 플로이드-워셜(Floyd-Warshall)에 대해서 문제의 유형별로 어떤 알고리즘을 사용하면 좋을지, 그리고 각각의 특징과 풀이방법을 알아보자.

 

 

다익스트라(Dijkstra)

: 다익스트라는 특정 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘이다. (single source shortest path problem)

A->B의 최단거리 = A->b의 최단거리 + b->B의 가중치 임을 활용하여 문제를 푸는 방식으로, 대체로 다음과 같은 유형에서 사용한다.

시간복잡도 = O(ElogE) (E: 간선의 갯수)

 

o 가중치가 있는 그래프에서 목적지까지 최단거리 찾기

: 2차원 배열로 그래프가 주어지고 각 좌표에 가중치가 있을 때, 출발지에서 인접한 좌표와 거리를 PriorityQueue(Python= heapq)에 추가하여 제일 가까운 순으로 경로를 선택해나간다. 그리고 2차원 배열에 (i,j)좌표까지의 최소거리를 저장하여 좌표까지 이동한 거리와 좌표의 가중치 합이 최소가 아니라면 선택하지 않는다.

        for n in range(4):
            ni, nj = i + di[n], j + dj[n]
            if ni >= 0 and ni < N and nj >= 0 and nj < N and dist[ni][nj] > arr[ni][nj] + d:
                dist[ni][nj] = arr[ni][nj] + d
                heapq.heappush(que, (dist[ni][nj], ni, nj))

[연습문제] 2021.07.09 - [Algorithm/문제풀이] - [Python][백준] 4485_녹색 옷 입은 애가 젤다지?

 

o 정점, 간선, 가중치가 주어졌을 때 정점간 최단거리 구하기

 : 위의 유형과 비슷하게, 특정 시작 정점에서 인접한 정점을 PriorityQueue(Python= heapq)에 추가하여 가까운 정점 순으로 선택한다.

A->B (dist) 정보는 arr[A][B] = dist 로 하거나 arr[A]에 append([B, dist]) 할 수 있다.

        for a in arr[start]: # [end, d]
            next = a[0]
            if dist[next] > a[1] + start:
                dist[next] = a[1] + start
                heapq.heappush(que, (dist[next], next))

[연습문제] 2021.07.09 - [Algorithm/문제풀이] - [Python][백준] 1916_최소비용 구하기

 

단, 음의 가중치가 있을때는 다익스트라를 사용할 수 없고, 벨만-포드(Bellman-Ford) 알고리즘을 사용해야 한다.

간선의 수가 너무 많거나 정점의 갯수가 적을 떄는 우선순위 큐 대신 일반 큐를 사용하는게 더 빠를 때도 있다.

---

벨만-포드(Bellman-Ford)

: 음의 가중치가 있는 그래프에서의 최단거리를 구할 떄 사용한다.

단, 음의 가중치 경로가 사이클을 이루면 이 알고리즘을 적용할 수 없다.

(사이클의 경로를 이동할 때 마다 소요시간이 줄어듬. dist[i] 값이 무제한 업데이트됨)

 

 

(1) 출발지->n 최단거리를 d[n]이라고 할 때, 모든 간선을 선택해보며 d[n]을 최소값으로 업데이트한다 (E번 반복)

(2) 업데이트되는 d[n]이 없을 때까지 이를 반복한다. (순환을 포함하지 않기 때문에 최대 V-1번 반복)

* V: 정점의 갯수, E: 간선의 갯수

 

o 음의 가중치가 있을 때 최단 거리

    # N-1 * M 번 벨만포드로 dist배열 업데이트
    for n in range(N-1):
        for i in range(N):
            for j, d in arr[i]:
                if dist[i] != sys.maxsize and dist[i] + d < dist[j]:
                    dist[j] = dist[i] + d

o 음의 사이클이 발생하는지 구하기

    # (도달가능한!) 음의 사이클이 존재하는지 확인
    # (N-1 수행 후 dist배열 업데이트 발생여부)
    for i in range(N):
        for j, d in arr[i]:
            if dist[i] != sys.maxsize and dist[i] + d < dist[j]:
                # negative weight cycle

[연습문제] 2021.07.15 - [Algorithm/문제풀이] - [Python][백준] 11657_타임머신

 

최대 V-1번  갯수만큼 모든 간선 E를 탐색하기 때문에 시간복잡도는 O(V * E)이고, E는 최대 V^2이기 때문에 즉 O(V^3)이 된다. 이는 당연히 다익스트라보다는 느린 속도이다.

---

플로이드-워샬(Floyd-Warshall)

: 플로이드-워셜은 모든 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘이다. (all pairs shortest path problem)

원리는 i->j 로의 최단거리를 0~N 정점을 중간지점 k라고 했을 때, i->k 최단거리 + k->j 최단거리와 비교하면서 모든 정점의 최단거리값을 업데이트 하는 것이다.

 

최단거리를 저장하는 2차원 배열을 dist[][] 라고 하면, dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 로 나타낼 수 있다. 

코드에서는 3중 for문으로 구현된다.

# Floyd-Warshall
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j])

[연습문제] 2021.07.16 - [Algorithm/문제풀이] - [Python][백준] 11404_플로이드