🛵

[JS] Single-Source Shortest Paths


Shortest path(최단 경로) 문제는 주어진 그래프에서 두 정점을 연결하는 가장 짧은 경로의 길이를 찾는 문제다.

그래프에서 최단 경로를 찾는 문제를 해결할 때 가장 중요한 것은 음수 가중치를 갖는 간선이 있는지 여부다. 음수 간선이 존재하면 음수 사이클이 생길 수 있는데, 음수 사이클이 생기면 경로의 길이가 -Infinity까지 발산할 수 있기 때문이다. 음수 사이클이 있는 그래프에서는 어떤 최단 경로 알고리즘도 최단 경로를 정확히 찾을 수 없다.

그래프의 종류와 특성에 따라 많은 최단 경로 알고리즘이 존재하지만, 여기서는 단일 시작점 최단 경로(Single-Source Shortest Paths) 알고리즘 두가지를 볼 것이다.

Dijkstra

다익스트라 알고리즘은 그래프에 음수 간선이 없을 때 사용할 수 있다. 한 노드에서 다른 노드들까지 최단 거리를 구할 수 있다.

현실 세계는 음의 간선이 존재하지 않기 때문에 현실 세계에 사용하기 매우 적합한 알고리즘 중 하나다.

다익스트라 알고리즘은 '그리디'한 접근을 사용한다. 시작점 u에서 시작해서 점점 확장해 나가면서 다른 노드까지의 최단 경로를 갱신한다. 시작점에서 가까운 순서대로 정점을 방문하는 것이 BFS와 비슷하지만, 현재 확정한 경로와 연결된 모든 노드를 조사하는 것이 아닌 가장 가중치가 작은 노드를 선택한다는 점이 다르다.

이때 가장 가중지차 작은 노드를 선택하기 위해 우선순위 큐를 사용한다.

구현

먼저 각 정점까지의 최단 거리를 저장하는 배열 dist를 만들고 시작점은 0, 다른 노드들을 Infinity로 초기화한다. 시작점부터해서 정점을 방문할 때마다 인접한 정점을 모두 검사한다. 만약 현재까지 가중치에 간선의 가중치를 더한 값이 인접한 정점의 가중치보다 작은 경우, 최단 거리를 갱신해주고 [노드, 가중치]쌍을 우선순위 큐에 넣어준다.

이때 우선순위 큐 안에 있는 노드의 가중치 정보와 dist에 있는 정보가 불일치 하는 경우가 발생할 수 있다. 이 경우는 우선순위 큐에서 노드가 나왔을 때, 가중치가 dist의 가중치보다 크면 더 짧은 경로가 발견됐다는 의미기 때문에 무시해주면 된다.

다익스트라 알고리즘은 각 정잠마다 인접한 간선들을 탐색하는 과정과 우선순위 큐에 다음 확인할 노드를 넣고 빼는 과정으로 나뉜다. 따라서 O(E)+O(ElogE)=O(ElogE)O(E) + O(E \log E) = O(E \log E)의 시간복잡도를 가진다.

1function dijkstra(n, edges, src) {
2 const adjList = Array.from(Array(n), () => []);
3 const dist = Array(n).fill(Infinity);
4 edges.forEach(([u, v, w]) => adjList[u].push([v, w]));
5
6 const pq = new MinHeap();
7 pq.push([src, 0]);
8 dist[src] = 0;
9 while(pq.heap.length) {
10 const [cur, weight] = pq.pop();
11 // 더 짧은 경로가 발견됐다면 무시
12 if(dist[cur] < weight) continue;
13 adjList[cur].forEach(([next, nextWeight]) => {
14 if(dist[next] > weight + nextWeight) {
15 dist[next] = weight + nextWeight;
16 pq.push([next, weight + nextWeight]);
17 }
18 });
19 }
20
21 return dist;
22}

Bellman-Ford

벨만-포드 알고리즘은 그래프에 음수 간선이 있을 때도 한 노드에서 다른 노드까지 최단 거리를 구할 수 있다.

이 알고리즘은 노드의 수 - 1번 간선들을 검사해서 노드까지 최단 거리를 갱신한다. 노드의 수 - 1번 확인하는 이유는 가장 먼 거리의 노드까지 도달하는 데 필요한 간선의 수가 노드의 수 - 1이기 때문이다. 다익스트라 알고리즘과는 다르게 모든 간선을 탐색하기 때문에 일반적으로 더 느리다.

벨만-포드 알고리즘은 특이하게도 그래프에 음수 사이클이 있는지 판별할 수 있다. 노드의 수 - 1 번 간선들을 검사한 상태에서 다시 간선들을 검사했을 때 어느 노드던 최소 경로가 갱신되면 음수 사이클이 있음을 알 수 있다.

구현

다익스트라와 같이 정점까지의 최단 거리를 저장하는 배열 dist를 만들고 시작점은 0, 다른 노드들을 Infinity로 초기화한다. 간선을 n - 1번 검사하면서 dist에 저장된 가중치보다 새로 계산한 가중치가 더 작다면 갱신해준다.

벨만-포드 알고리즘은 정점의 수만큼 모든 간선을 탐색하기 때문에 O(VE)O(VE)의 시간 복잡도를 가진다.

1function bellmanFord(n, edges, src) {
2 const dist = Array.from(Array(n), () => Infinity);
3 dist[src] = 0;
4 for(let iter = 0; iter < n - 1; iter++) {
5 edges.forEach(([from, to, weight]) => {
6 if(dist[to] > dist[from] + weight) {
7 dist[to] = dist[from] + weight;
8 }
9 });
10 }
11 for(let [from, to, weight] of edges) {
12 if(dist[to] > dist[from] + weight) return null;
13 }
14 return dist;
15}

참조:
https://m.blog.naver.com/ndb796/221234424646
프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략