최단 거리(Shortest Path)

정의

특징

SSSP & APSP

• Single-Source Shortest Path
• 한 점으로부터 다른 모든 점에 대한 최단 거리 구하기
• Dijkstra, Bellman-Ford

• All-Pair Shortest Path
• 서로 다른 모든 두 점에 대한 최단 거리 구하기
• Floyd-Warshall

• 이외에도 그래프의 개형(양방향/단방향, 트리 DAG 등)에 따라서 다른 방법을 사용

Shortest Path in weigted graph

Dijkstra’s Algorithm

Greedy Approach

• 가중치가 0 이상인 그래프에서 최단 거리(SSSP)를 구하는 알고리즘

• 정점의 종류를 두 개로 나눈다. (최단 거리가 확정된 정점, 확정되지 않은 정점)

• 시작점의 거리는 0, 다른 정점들은 ∞로 초기화(R = {V0}, dist[V0] = 0)
• 0번 정점에서 시작, R은 최단 거리가 확정된 정점의 집합

• |R| < V인 동안, u ∉ R이면서 dis[u]가 최소인 u를 고른 뒤, R = R ∪ {u}

• u와 인접하고 w ∉ R인 w에 대해서, dist[w] = min(dist[w], dist[u] + eu,w)로 갱신

정당성 증명 1

• u ∉ R이면서 dist[u]가 최소인 u를 고른 뒤, R = R ∪ {u}

• dist[u]가 최단 거리가 아니라면, v ∉ R인 v를 거치는 더 좋은 최단 경로가 존재함.

• dist[u] = dist[v] + eu,v이고, 모든 가중치는 0 이상이므로 dist[v] ≤ dist[u]

• dist[v] = dist[u]인 경우, 바꿔도 답

• dist[v] < dist[u]인 경우, u ∉ R이면서 dist[u]가 최소인 u를 고르므로 모순이다.

정당성 증명 2

• u와 인접하고 w ∉ R인 w에 대해서, dist[w] = min(dist[w], dist[u] + eu,w)로 갱신

• 0 - … - u - … - w와 같은 경우는 고려하지 않아도 되는가?

• u를 포함하지 않는 Source - … 경로가 존재함, u를 거쳐가면 거리가 증가하게 된다.

• 이전에 확정될 때 고려된 적이 있기 때문에 지금 확정된 u와 인접한 노드만 확인하면 된다.

음수 가중치 간선이 존재하면 안되는 이유

• Dijkstra Algorithm: 그리디 전략 사용

• 한 번 확정한 최단 거리는 다시 갱신하지 않음

• 그래프가 음의 사이클을 가지고 있는 경우(간선의 가중치의 합이 음수인 사이클)

• 간선을 무한히 돌아 가중치를 계속 낮출 수 있음

• Bellman-Ford Algorithm: 음수 가중치에서도 작동, O(VE)

구현

• |R| < V인 동안, u ∉ R이면서 dist[u]가 최소인 u를 고른 뒤, R = R ∪ {u}
• 최소를 고르는 것 O(V), 확정하는 연산O(1)
• 최소를 고르는 것 O(logV): Priority Queue

• u와 인접하고 w ∉ ㄱR인 w에 대해서, dist[w] = min(dist[w], dist[u] + eu,w)로 갱신
• 최대 E번 갱신, 각 노드를 한번씩만 보고, 해당 노드에 붙어있는 간선만큼 확인해야 하므로

• INF 값이 충분히 크지 않은 경우

• 방문한 정점을 다시 방문하는 경우

• 우선순위 큐에 거리가 아닌 간선의 가중치를 넣는 경우

백준 문제

• 1753 최단경로
• Dijkstra’s Algorithm을 직접 구현

• 11779 최소비용 구하기 2
• 최단 경로를 직접 구하는 문제(역추적)
• 알고리즘은 최단 거리를 확정하고 다시 보지 않는다는 점에서 아이디어를 찾아보자

• 1854 K번째 최단경로 찾기
• 그래프가 주어졌을 때, 1번 도시에서 각 도시로 가는 K번째 최단 경로의 가중치의 합 구하기
• 알고리즘에 대한 깊은 이해가 필요

특수한 경우의 최단 거리 찾기

• 단순 DFS / BFS로 찾을 수 있음 O(V + E)

• 물론 0 이상의 가중치를 가지므로, Dijkstra를 사용할 수 있음
• O (E logV)

• 0 - 1 BFS Approach
• 기본 BFS를 통해 최단 거리를 구하자
• 큐에 들어간 정점들의 가중치는 정렬되어있음
• O (V + E)

All-Pair Shortest Path

• 그래프상의 모든 정점에 대해서, 서로 다른 두 정점 간의 거리 구하기

• 앞에서 배운 Dijkstra를 모든 정점에 대해서 탐색: O(E logV x V)

• 간선은 O(V^2)개 존재, 시간복잡도는 O(V^3 logV)

Floyd-Warshall: DP Approach

• 정점 k에 대한 정보를 알고 있다면, 그 정보로 k + 1번째 정점에 대해서도 알 수 있을까?

• 정점에 번호를 1, 2, …, V로 번호를 매긴 뒤, 다음과 같은 DP를 생각해보자

• d[k][i][j]: 1번 정점부터 k번 정점까지만 중간 경로로 사용해서 i에서 j로 가는 최단거리

• d[k - 1][i][j]로부터 d[k][i][j]를 도출해보자

• Base Case
• d[0][i][j]: i번 정점에서 j번 정점으로 가는 경로가 있다면 가중치, 그렇지 않다면 ∞

• Step: i → j로 가는 가능한 모든 경로의 집합을 두가지로 나눌 수 있다.
1. k번째 노드를 거쳐가는 경우
2. k번째 노드를 거쳐가지 않는 경우

• 두가지 경우밖에 없으므로, 이 중 작은 값으로 갱신하면 된다.

1. k번째 노드를 거쳐하는 경우
1. k는 두번 이상 나타나지 않는다. 만약 두번 나타난다면, 한번만 나타나도록 경로를 수정할 수 있고, 해당 경로가 이루는 거리가 더 작다
2. 따라서 (i → k) + (k → j)와 같다.

2. k번째 노드를 거쳐가지 않는 경우
1. d[k][i][j]는 1번 정점부터 k번 정점까지를 중간 경로로 사용해서 i → j로 가는 최단 거리
2. k번째 노드를 사용하지 않았으므로, d[k - 1][i][j]와 같다.

구현

• O (V^3)이기 때문에, 문제에서 대부분 V ≤ 500 정도로 주어진다.

• 연결 리스트로 구현하는 것보다 인접 행렬로 구현하는 것이 일반적이고 편리

• 최단 거리 배열을 만드어나갈 때, k번째 정점을 생각한다면 k - 1번째만 확인하면 된다.

• 모든 k에 대한 거리를 저장하는 것보다, 바로 직전 것 (k - 1)만 저장하면 더 효율적

• 공간복잡도를 V^3에서 2 x V^2로 줄일 수 있다.

• 갱신되기 전 값을 가져간 뒤, 갱신한 값을 배열에 넣어야 한다.

• 업데이트 이후 값을 가져가서 계산하면 정답이 나오지 않을 것

• 갱신 여부를 알지 못하기 때문에 두개의 층을 번갈아가며 사용

• d[k - 1][i][k]와 d[k][i][k], d[k - 1][k][j]와 d[k][k][j]가 서로 다를 수 있을까?

• d[k][i][j]: 1번 정점부터 k번 정점까지만 중간 경로로 사용해서 i에서 j로 가는 최단 거리

• i → k 또는 k → j로 갈 때, 중간 노드로 k를 사용할 수 없음

• 따라서 2차원으로 나타냈을 때 d[i][j]는 갱신되지 않았고, 공간복잡도를 V^2까지 줄인다.

• 11404 플로이드
• 같은 정점 쌍에 대해서 여러개의 간선이 들어오므로 가장 작은 가중치만 저장

출처