가중치 있는 최단 경로 문제

Dijkstra

def dijkstra(sx):
    dist = [INF]*n; dist[sx] = 0
    # (cost, x) 저장하는 min-heap
    hq = []; heapq.heappush(hq, (0, sx))
    while hq:
        cost, x = heapq.heappop(hq)

        if cost > dist[x]: continue

        for nx, weight in adj[x]:
            newCost = cost + weight
            if newCost < dist[nx]:
                dist[nx] = newCost
                heapq.heappush(hq, (newCost, nx))

    return dist

0 이상의 가중치를 갖는 그래프에 대해 한 정점으로부터의 최단거리 계산

 

요약

BFS와 비슷하지만 3가지가 다르다

① (cost, node)를 저장하는 우선순위 큐를 사용한다

② 거리가 갱신될 때마다 큐에 넣는다

③ 큐에서 꺼낸 cost가 최단거리가 아니라면 버린다

 

시간복잡도

$O(|E| \log{|E|}) = O(|E| \log{|V|})$ : 각 간선 1번씩 검사 and 우선순위 큐에 최대 |E|번 원소 삽입, 삭제

 

예제

https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

Bellman-Ford

def bellmanFord(s):
    INF = 10**9
    dist = [INF] * (n+1)
    dist[s] = 0
    updated: bool
    # n번 순회
    for i in range(n):
        updated = False
        # 모든 간선에 대한 relax 시도
        for x in range(1, n+1):
            for y, cost in adj[x]:
                if dist[y] > dist[x] + cost:
                    # relax
                    updated = True
                    dist[y] = dist[x] + cost

        # 더이상 relax가 이루어지지 않는다면 종료
        if not updated:
            return upper

    # n번째 순회에서 relax가 이루어진다면 음수 사이클 존재
    return []

임의의 가중치를 갖는 그래프에 대해 한 정점으로부터의 최단거리 계산

(단, 음수사이클이 존재할 경우 empty list 반환)

 

요약

relaxation : 조금 더 좋은 경로를 발견하는 것

 

지금까지 알고 있던 경로 $sx \rightsquigarrow y$ 보다 새로운 경로 $sx \rightsquigarrow x \rightarrow y$ 가 더 좋다!

$\Rightarrow$ dist[y] > dist[x] + w(x, y)

 

그럼 새로운 경로 $sx \rightsquigarrow x \rightarrow y$ 를 학습한다!

$\Rightarrow$ dist[y] = dist[x] + w(x, y)

 

1. 먼저 음수 사이클이 존재하지 않는 경우를 생각해보자.

 

최단 경로를 그려놓고 생각해보자. 최단 경로에는 사이클이 존재하지 않는다.

 

$sx \rightarrow x_1 \rightarrow x_2$

 

최단 경로니까 $trueDist[x_1] = dist[sx] + w(sx, x_1)\ $ and $trueDist[x_2] = trueDist[x_1] + w(x_1, x_2)$ 가 성립할 것이다.

 

실제로 relaxation 이 모든 간선에 대해 1번씩 이루어지고 나면 relaxation의 순서와 무관하게 $dist[x_1] = dist[sx] + w(sx, x_1)$ 이 계산된다. 따라서 $dist[x_1] = trueDist[x_1]$ 이 성립한다.

 

여기서 다시 relaxation 이 모든 간선에 대해 1번씩 이루어지고 나면 relaxation의 순서와 무관하게 $dist[x_2] = trueDist[x_1] + w(x_1, x_2)$ 가 계산된다. 따라서 $dist[x_2] = trueDist[x_2]$ 가 성립한다.

 

따라서, 이 과정을 최대 $|V| - 1$번만 반복하면 모든 정점에 대해 올바른 최단 거리를 구할 수 있다.

 

2. 음수 사이클이 존재하는 경우를 생각해보자.

 

음수 사이클이 존재하는 경우 relaxation이 무한히 발생한다. 따라서 |V| 번째에도 relaxation이 발생한다.

 

이는 $x_1 \leftrightarrow x_2$ 이고 가중치 -1인 경우를 생각해보면 쉽게 확인할 수 있다.

 

시간복잡도

$O(|V||E|)$ : 각 정점에 대해 모든 간선 검사

 

예제

https://www.acmicpc.net/problem/11657

11657번: 타임머신

https://www.acmicpc.net/problem/1865

1865번: 웜홀

 

참고

INF를 설정하는 방법이 두 가지 있는데 각각 장단점이 있다.

 

① INF = float('inf')

장점

- 시작 정점으로부터 도달 가능 여부를 dist[x] != INF 로 확인할 수 있다.

단점

- 시작 정점과 연결되지 않은 정점들에 대해서는 항상 dist 값이 INF로 유지되어 절대로 relax가 이루어지지 않는다. 

- 따라서, 이 정점들 사이에 존재하는 음수사이클은 찾지 못한다.

 

② INF = pow(10, 9)

장점

- 시작 정점과 연결되지 않은 정점들에서도 relax가 이루어진다. 

- 따라서, 이 정점들 사이에 존재하는 음수사이클도 찾을 수 있다.

단점

- 시작 정점으로부터 도달 가능 여부를 dist[x] != INF 로 확인할 수 없다.

- 시작 정점으로부터 도달 가능 여부를 dist[x] < INF - (적당히 큰 값) 으로 확인해야 한다.

 

Floyd

def floyd(adj):
    dist = [row[:] for row in adj]

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

    return dist

모든 정점 쌍에 대한 최단거리 계산

 

요약

dist[k][u][v] : 0번 정점 ~ k번 정점까지만 경유점으로 사용 가능할 때 u $\rightarrow$ v 최단 경로의 길이

dist[k][u][v] = min(dist[k-1][u][k] + dist[k-1][k][v], dist[k-1][u][v])

 

dist[k-1][u][k] == dist[k][u][k] 임을 이용하면 (3차원 DP) $\rightarrow$ (2차원 DP) 로 차원 축소 가능

 

dist[u][v] : 0번 정점 ~ k번 정점까지만 경유점으로 사용 가능할 때 u $\rightarrow$ v 최단 경로의 길이

dist[u][v] = min(dist[u][k] + dist[k][v], dist[u][v])

 

시간복잡도

$O(|V|^3)$ : 각 정점에 대해 모든 간선 검사

 

예제

https://www.acmicpc.net/problem/11404

11404번: 플로이드