[Algorithm] Priority Queue & Shortest Path Algorithm(다익스트라, 벨만 포드, 플로이드 워셜) 정리 + 추천 문제 list

0. 들어가며

이번 주에는 Priority Queue(Heap)과 최단경로 알고리즘(다익스트라, 벨만포드, 플로이드 워셜) 알고리즘에 대해서 공부했습니다.

저는 알고리즘을 공부하며 크게 2가지의 알고리즘이 있다고 생각하는데요. 바로 찐 알고리즘과 그외 입니다.

찐 알고리즘은 바로 누군가가
"특정 상황에 적용 가능한 일련의 규칙이나 여러 행위 그리고 더 나아가 공식화한 형태로 표현한 것"
이라고 생각합니다. 

예를 들면 다익스트라, 크루스칼, A* 알고리즘 등이 있습니다. 

언급된 알고리즘들은 "특정 상황"에서 "일련의 규칙이나 여러 행위"하면 원하는 결과를 얻을 수 있습니다.

 

오늘 배울 알고리즘인 다익스트라, 벨만 포드, 플로이드 워셜의 경우 "찐 알고리즘"으로 어떤 상황에서, 어떻게 구현하면 좋은지에 집중하며 글을 읽어주시면 감사하겠습니다.

---

1. Dijkstra(다익스트라) 알고리즘

Dijkstra 알고리즘은 Dijkstra라는 사람이 만들어낸 최단경로를 알아낼 수 있는 알고리즘입니다.

Dijkstra 알고리즘은 다음과 같은 상황에서 사용할 수 있습니다.

 

"1개의 시작 정점 $s$으로부터 나머지 정점들까지의 최단 경로를 알아내고 싶고, 음수 사이클이 존재하지 않은 Graph인 경우"

 

보통 다익스트라 알고리즘은 음수 가중치를 가질 경우 사용할 수 없다고 생각하지만, 사실은 사용할 수 있습니다. 다만, 음수 사이클이 발생한 경우를 판별하지 못하고 무한 loop에 빠지기 때문에 일반적으로 사용할 수 없습니다. 하지만 만약 음수 사이클이 무조건 없다면? 다익스트라 알고리즘을 이용해 갱신할 수 있습니다. (하지만 보통 음수 가중치 간선이 존재하지만, 음수 사이클이 없다는 것을 보장하는 문제는 잘 없습니다...)

 

다른 예로

단순 BFS를 이용해 시작 정점 $s$으로부터 나머지 정점들까지의 최단 경로를 알아낼 수 있습니다.

직관적으로 가능한 것이 이해될 것입니다. 하지만 우리가 단순 BFS보다 다익스트라 알고리즘을 사용하는 이유는 단순 BFS를 사용했을 때, 최악의 경우 같은 노드에 대해 갱신 과정이 계속 진행되어 갱신을 위한 노드들이 저장된 Queue에 굉장히 많이 쌓이게 되어 시간복잡도가 더 높아지기 때문입니다. 따라서 Queue에 많이 쌓이지 않는 다는 것을 보장할 수 있다면, 단순 BFS를 다익스트라 대신 최단경로를 알아내는데 사용해도 됩니다. (보통 모든 가중치가 같은 배열 탐색이 이에 해당 합니다.)

 

1. 1 Dijkstra 알고리즘의 일반적인 구현 방법

• 우선순위 큐(Priority Queue, Heap)를 사용한 너비우선 탐색
  • 일반적으로 너비우선 탐색을 위해서는 Queue를 사용하게 됩니다. 하지만 Dijkstra를 구현할 때는 일반적으로 Priority Queue를 사용하게 됩니다.
• 구현 시 유의 사항
  • 먼저 PQ(Priority Queue)에 들어갔지만, 해당 노드가 고려되기 전에 다른 간선에 의해 더 짧게 갱신된 노드와 가중치 값이 PQ에 들어갈 예정이라면 이를 어떻게 처리하는가?
    1. 우선순위 큐 내에서 해당 정점을 갱신하는 원소를 찾아 현재 PQ를 잘 탐색해서 PQ내의 원소와 교환한다.
    2. 기존의 정점과 가중치는 그대로 두고, PQ에 넣은 뒤, 나중에 먼저 정점과 가중치는 나중에 들어간 가중치가 높은 원소가 고려되었으므로, 이를 무시한다

                     보통 2번을 선택하게 됩니다. 1번은 구현과 시간 복잡도 상 어렵기 때문

• 시간 복잡도는 $O(E\log E)$ 혹은 $O(E\log V)$로 표기합니다.

1. 2 Dijkstra 알고리즘의 정당성 증명

Dijkstra 알고리즘과 같은 "찐 알고리즘"은 해당 알고리즘이 왜 이렇게 되는지 증명을 아는 것 또한 문제를 푸는데 도움이 됩니다. 코테가 급하지 않다면 한번쯤 이해하고 넘어가셔도 좋을 듯 합니다.

※ 본 증명은 알고리즘 문제 해결 전략 책의 내용을 발췌했음을 밝힙니다.

• 만약 다익스트라 알고리즘을 진행하는 중에 아직 제대로 최단 경로를 갱신 못한 정점 $u$가 있다고 가정해보겠습니다. 만약 PQ가 $u$를 꺼내는 순간 지금까지 "방문 완료"된 정점들과 "방문 미완료"된 정점들의 집합들로 전체 정점 집합을 분할 가능합니다.
  이때 $u$에 대해 최단 거리를 잘못 계산했다는 말은 다익스트라 알고리즘이 진행되며 만든 Spanning Tree에서의 경로보다 더 짧게 방문 가능한 경로가 존재한다는 뜻입니다.
• PQ의 TOP에 저장된 갱신되지 않은 정점을 $p$, 해당 $p$ 직전에 완료된 정점을 $q$, 시작 정점으로부터 최단경로가 저장된 배열을 $dist[idx]$라 해보겠습니다. 따라서 우리는 $dist[p] = dist[q] + w(u, p)$라 할 수 있습니다.
  그런데 $p$는 $u$가 방문되기 전에 나온 정점이므로 $u$보다 우선순위(최단 거리가 짧다)가 높습니다. 고로 무조건 적으로 $u$가 $p$에 비해 우선순위가 낮으므로 처음에 가정했던 최단경로를 갱신하지 못한 $u$가 나올 수 없으므로 이전에 먼저 최단 경로가 갱신되었고, 이는 가정에 모순입니다.

 

※ 기존의 제 지식으로는 음수 가중치에서도 다익스트라가 가능하다고 이해하고 있었습니다.
하지만 음수가중치가 가능한 그래프가 무조건적으로 음수 사이클이 없다는 것을 보장하기 어렵기 다는 이유로 사용하지 않는다 이렇게 이해하고 있었습니다.

 

먼저 음수 가중치가 있는 그래프(음수 가중치 사이클 존재 o)에서 PQ로 구현한 다익스트라 최단경로 알고리즘이 왜 동작하지 않는지 알아보겠습니다.

만약 음수 사이클이 있다면, 이는 무한히 해당 사이클을 통해 각 노드들이 최단경로를 갱신할 수 있다는 뜻이고, PQ에 무한히 쌓이게 되어 무한 루프가 진행될 것입니다. 

 

다음으로 음수 가중치가 있는 그래프(음수 가중치 사이클 존재 x)에서 다익스트라를 사용하면 어떻게 될까요?

웃기지만, 사용 가능합니다. 다만 주의할 점이 많습니다.

1. 위의 증명 방식을 통해 PQ에서 튀어나온 정점의 경우 이후 Step에서 갱신이 되지 않는 것을 알게되었습니다. 하지만 음수 가중치 간선이 있는 경우 이미 최단 경로가 갱신된 정점이 다시 PQ로 들어가 갱신될 수 있습니다.
2. 이로 인해 기존의 $E\log E$의 시간 복잡도를 넘어서게 되고, 자료를 찾아보니 최악의 경우 지수 복잡도를 갖게 됩니다.
3. 즉, 음수 가중치를 가졌을 때 다익스트라를 사용하는 것은 기도를 해서 지수 복잡도를 가지게 되는 그래프가 입력으로 들어오지 않도록 기도를 해야합니다.

 

우리는 문제를 

 

 

 

 

하지만 일반적으로 위의 방식대로 구현이 되지 않았다는 것을 스터디를 하며 알게 되었습니다.

보통 $dist[next] > dist[now] + weight$의 조건문을 통해 PQ에 해당 정점을 넣을지 말지를 정하게 됩니다. 

2. Bellman-Ford(벨만 포드) 알고리즘

Bellman-Ford 알고리즘은 Bellman-Ford라는 사람이 만들어낸 최단경로를 알아낼 수 있는 알고리즘입니다.

Bellman-Ford 알고리즘은 다음과 같은 상황에서 사용할 수 있습니다.

 

"1개의 시작 정점 $s$으로부터 나머지 정점들까지의 최단 경로를 알아내고 싶고, 음수 사이클이 존재하는 Graph인 경우"

 

보통 벨만포드의 경우 간선 가중치에 음수가 존재하고, 1개의 정점에서 다른 나머지 정점으로의 최단 경로를 알아내고 싶은 경우 사용하는 알고리즘입니다. 

벨만 포드 알고리즘이 알아내는 것은 크게 2가지 입니다.

• 1개의 정점에서 나머지 정점으로의 최단 경로
• 음수 사이클의 존재 여부 판별

즉, 음수 사이클이 ~~하고 ~~하는지 이런걸 알아내는게 아니라, 음수 사이클이 존재하는지? 약간의 트릭을 더하면 시작정점에서 원하는 정점까지 가는 경로에 음수 사이클에 도달 가능한지? 등을 알아낼 수 있습니다.

 

2. 1 Bellman-Ford(벨만 포드) 알고리즘의 일반적인 구현

• 모든 노드에서 인접 노드로의 갱신을 N - 1번 진행하면 모든 정점들의 최단 경로는 갱신됩니다. 이때 1번 더 진행하게 되면 음수 사이클을 가진 노드들만 갱신되게 됩니다. 나머지들은 이미 갱신될 거는 다 갱신됐기 때문입니다.
• 시간 복잡도 $O(VE)$

2. 2 Bellman-Ford(벨만 포드) 알고리즘의 정당성 증명

쉽게 위의 방식이 가능한 것을 증명하자면, $st \rightarrow ed$의 최단 경로는 최악의 경우 전체 노드를 통해 표현 가능하고 전체 노드 수를 $V$라 할 때, 간선의 수는 $V-1$개 입니다. 따라서 각 간선을 갱신하는 과정을 $V - 1$번 반복하면 됩니다.

 

3. Floyd-Warshall(플로이드 와셜) 알고리즘

Floyd-Warshall 알고리즘은 다음과 같은 상황에서 사용할 수 있습니다.

 

"N개의 시작 정점 $s$으로부터 나머지 정점들까지의 최단 경로를 알아내고 싶고, 음수 사이클이 존재하지 않은 Graph인 경우"

 

플로이드 와셜 알고리즘은 모든 정점과 정점간의 거리를 알 수 있게하는 최단경로 갱신 알고리즘입니다.

3.1 Floyd-Warshall(플로이드 와셜) 알고리즘의 일반적인 구현

• 정점 갯수 $V$에 관한 3중 for loop으로 쉽게 구현
• 시간 복잡도 $O(V^3)$

3. 2 Floyd-Warshall(플로이드 와셜) 알고리즘의 정당성 증명

• 두 정점 $u, v$를 잇는 어떤 경로가 있다고 가정해보겠습니다. 이 경로는 항상 시작점 $u$와 끝점 $u$를 지납니다. 해당 경로가 아니지만, $u, v$를 잇는데 더 짧은 거리로 경유할 수 있는 경유점도 있다고 하겠습니다. 이 경유점을 $p$라고 해보겠습니다.
• 이때 기존 고려 중인 정점 집합 $S$를 이용해 $u, v$를 잇는 거리를 알려주는 함수를 $D_s(u, v)$라 하겠습니다.
• 이제 정점 집합 $S$ 뿐만 아니라 외부의($S$에 속하지 않는 정점) $p$도 이용해 보겠습니다. 이때 만약 $D_{s +p}(u, v)$가 기존의 $D_s(u, v)$보다 짧다면 해당 $S$정점에 $p$를 포함 시킨 후 최단 경로를 갱신할 수 있습니다. 이와 같은 정점 $S$가 최종적으로 모든 정점을 포함하게 된다면 이는 "모든 정점을 활용해 $u$에서 $v$로의 최단 거리를 알려주는 함수 $D_{all}(u, v)$로 표기하고 이는 우리가 알고자하는 $u$에서 $v$까지의 최단 거리"임을 알 수 있습니다.

 

4. 추천 문제 list

※ 설명은 추후 추가하겠습니다.

4. 1 BOJ 11286 절대값 힙

11286번: 절댓값 힙

import sys
from heapq import heappop, heappush
get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())

N = None
heap = None
def set_variable():
    global N, heap
    N = get_input()
    heap = []

def solution():
    global N, heap
    def abs_smaller_priority(item):
        return abs(item), item
    for _ in range(N):
        x = get_input()
        if x == 0:
            if heap : 
                print(heappop(heap)[1])
            else:
                print(0)
        else:
            heappush(heap, abs_smaller_priority(x))
            

if __name__ == "__main__":
    set_variable()
    solution()

4. 2 BOJ 1754번 최단 경로

1754번: 진영 순열

import sys
import math
from heapq import heappush, heappop

get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())

V, E, K = None, None, None
dist = None
edge = None
heap = None


def set_variable():
    global V, E, K, dist, edge, heap
    V, E = get_line()
    K = get_input()
    edge = [[] for _ in range(V + 1)]
    dist = [math.inf for _ in range(V + 1)]
    heap = []
    for _ in range(E):
        u, v, w = get_line()
        edge[u].append((v, w))
    
        


def solution():
    def dijkstra():
        global V, E, K, dist, edge, heap
        dist[K] = 0
        heap.append((0, K))
        
        while heap:
            n_dist, n_pos = heappop(heap)
            
            if dist[n_pos] < n_dist:
                continue
            
            for nxt_pos, weight in edge[n_pos]:
                if  dist[nxt_pos] > n_dist + weight:
                    dist[nxt_pos] = n_dist + weight
                    heappush(heap, (dist[nxt_pos], nxt_pos))
    
    dijkstra()
    for i in range(1, V + 1):
        if dist[i] == math.inf:
            print("INF")
        else:
            print(dist[i])
        

if __name__ == "__main__":
    set_variable()
    solution()

 

4. 3 BOJ 1504 특정한 최단 경로

1504번: 특정한 최단 경로

import sys
import math
from heapq import heappush, heappop
get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())

N, E = None, None
edge = None

def set_variable():
    global N, E, edge
    N, E = get_line()
    edge = [[] for _ in range(N + 1)]
    for _ in range(E):
        a, b, c = get_line()
        edge[a].append((b, c))
        edge[b].append((a, c))

def solution():
    def dijkstra(st):
        global N, E, edge
        dist = [math.inf for _ in range(N + 1)] # dist[ed] => st에서 출발해 ed까지의 최단거리.
        dist[st] = 0
        heap = [(0, st)]
        
        while heap:
            n_dist, n_pos = heappop(heap)
            
            for nxt_pos, weight in edge[n_pos]:
                if dist[nxt_pos] > n_dist + weight:
                    dist[nxt_pos] = n_dist + weight
                    heappush(heap, (dist[nxt_pos], nxt_pos))
        
        return dist
    
    v1, v2 = get_line()
    v1_dist = dijkstra(v1)
    v2_dist = dijkstra(v2)
    
    answer = min(v1_dist[1] + v2_dist[N], v1_dist[N] + v2_dist[1])
    answer += v1_dist[v2]
    if answer >= math.inf:
        print(-1)
    else:
        print(answer)


if __name__ == "__main__":
    set_variable()
    solution()

4. 4 BOJ 1865 웜홀 

1865번: 웜홀

import sys

get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())

N, M, W = None, None, None
dist, adj = None, None


def set_variable():
    global N, M, W, adj, dist
    N, M, W = get_line()
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        S, E, T = get_line()
        adj[S].append((E, T))
        adj[E].append((S, T))
    for _ in range(W):
        S, E, T = get_line()
        adj[S].append((E, -T))
    dist = [sys.maxsize] * (N + 1)


def solution():
    global N, M, W, adj, dist

    def bellman_ford():
        dist[1] = 0
        check = False
        for i in range(N):
            for now_pos in range(1, N + 1):
                for nxt_pos, weight in adj[now_pos]:
                    if (dist[nxt_pos] > dist[now_pos] + weight):
                        dist[nxt_pos] = dist[now_pos] + weight
                        if i == N - 1:
                            check = True
        return check

    if bellman_ford():
        print("YES")
    else:
        print("NO")


if __name__ == "__main__":
    TC = get_input()
    for _ in range(TC):
        set_variable()
        solution()

4. 5 BOJ 11657 타임머신

11657번: 타임머신

import sys
import math

get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())

N, M = None, None
edge = None
dist = None

def set_variable():
    global N, M, edge, dist
    N, M = get_line()
    edge = [[] for _ in range(N + 1)]
    dist = [math.inf for _ in range(N + 1)]
    for _ in range(M):
        a, b, c = get_line()
        edge[a].append((b,c))


def solution():
    def bellman_ford():
        global N, M, edge, dist
        dist[1] = 0 # 시작 지점을 1로 잡음, 아무 곳이나 잡아도 상관없기 때문
        flag = True
        for i in range(N):
            for now_pos in range(1, N + 1):
                for nxt_pos, weight in edge[now_pos]:
                    if dist[now_pos] != math.inf and dist[nxt_pos] > dist[now_pos] + weight:
                        dist[nxt_pos] = dist[now_pos] + weight
                        if i == N - 1:
                            flag = False
        return flag

    flag = bellman_ford()
    
    if flag:
        for ans in dist[2:]:
            if ans == math.inf:
                print(-1)
            else:
                print(ans)
    else:
        print(-1)
        

if __name__ == "__main__":
    set_variable()
    solution()

4.6 BOJ 1738 골목길

1738번: 골목길

import sys
from collections import deque

get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())

n, m = None, None
adj = None
dist = None
parents = None
visited = None
cycle_check = None


def set_variable():
    global n, m, adj, dist, parents, visited, cycle_check
    n, m = get_line()
    dist = [-sys.maxsize for _ in range(n + 1)]
    adj = [[] for _ in range(n + 1)]
    parents = [0 for x in range(n + 1)]
    cycle_check = False
    for _ in range(m):
        u, v, m = get_line()
        adj[u].append((v, m))


def solution():
    global n, m, adj, dist, parents, cycle_check
    dist[1] = 0
    for i in range(n):
        for j in range(1, n + 1):
            for nxt, cost in adj[j]:
                if dist[nxt] < dist[j] + cost and dist[j] != -sys.maxsize:
                    dist[nxt] = dist[j] + cost
                    parents[nxt] = j
                    if i == n - 1:
                        dist[nxt] = sys.maxsize

    # tracking
    if dist[n] == sys.maxsize:
        print(-1)
    else:
        answer = []
        pos = n
        while pos != 0:
            answer.append(pos)
            pos = parents[pos]
        print(*answer[::-1])


if __name__ == "__main__":
    set_variable()
    solution()

 

4.7 BOJ 11404 플로이드

11404번: 플로이드

import sys

get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())

n, m, edge = None, None, None


def set_variable():
    global n, m, edge
    n = get_input()
    m = get_input()
    edge = [[sys.maxsize for _ in range(n + 1)] for _ in range(n + 1)]
    for _ in range(m):
        a, b, c = get_line()
        edge[a][b] = min(edge[a][b], c)

    for i in range(1, n + 1):
        edge[i][i] = 0


def solution():
    global n, m, edge

    def floyd_warshall():
        for m in range(1, n + 1):
            for s in range(1, n + 1):
                for e in range(1, n + 1):
                    if edge[s][m] != sys.maxsize and edge[m][e] != sys.maxsize:
                        edge[s][e] = min(edge[s][e], edge[s][m] + edge[m][e])

    floyd_warshall()
    for i in range(1, n + 1):
        ans_list = []
        for j in range(1, n + 1):
            if edge[i][j] == sys.maxsize:
                ans_list.append(0)
            else:
                ans_list.append(edge[i][j])
        print(*ans_list)

if __name__ == "__main__":
    set_variable()
    solution()

 

 

Tumbnail 😁