알고리즘 ] 다익스트라 알고리즘, 예제문제(백준 5719)

출처: https://www.acmicpc.net/problem/5719

정의

---

다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘이다. 

하나의 출발점을 기준으로 다른 모든 정점까지의 최단 거리를 구할 때를 활용한다.

참고)
다이나믹 프로그래밍(동적계획법)
: 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결 할 수 있을 때 사용한다.

 

특징 / 특이사항

---

음의 간선이 포함된 경우에는 사용할 수 없다. 

 

 

시간 복잡도

---

V : 정점의 갯수

E : 간선의 개수

 

각 정점마다 인접한 간선들을 탐색하는 과정 : O(E)

그래프의 모든 간선을 따라서 한번씩 검색을 하기때문에 모든 간선을 탐색하게 된다. 

 

우선순위 큐에 정보를 넣고 빼는 과정 : O(ElogE)

우선순위 큐에 데이터를 넣을 때 모든 간선이 한번씩 들어갈 수 있으므로 시간복잡도는 O(E)이다. 

우선순위 큐에서 데이터를 빼낼 때, O(logE)의 속도를 가지므로

데이터를 넣고 빼는 과정의 시간 복잡도는 O(ElogE)가 된다. 

참고)
javascript에서는 내장함수인 sort를 이용해서 구현하는데 
sort의 시간복잡도가O(logE)를 가진다.
https://brunch.co.kr/@k2u4yt/3

 

따라서 총 시간 복잡도는 O(E) + O(ElogE) = O(ElogE) 이다.

 

알고리즘 실행 순서

---

1. 시작 정점인 자신을 제외한 모든 정점까지의 거리를 무한대로 초기화 한다.
2. 시작 정점을 우선순위 큐에 삽입한다. 
3. 우선순위 큐에서 정점 하나를 꺼낸 후 해당 정점에서 갈 수있는 모든 인접한 정점들을 확인하여
   인접 정점까지의 거리가 기록된 거리보다 짧으면 거리값을 갱신하고
   거리 값이 갱신된 정점들을 우선순위 큐에 넣는다. 
4. 우선순위 큐에 더이상 정점이 없을 때까지 3~4번 과정을 반복한다.

 

---

Javascript 다익스트라 알고리즘 구현 방법

---

function dijkstra(graph, dists, start) {

    // 1. 첫 노드말고 모든 거리는 Infinity
	dists[start] = 0;
    // 2. 첫 노드를 우선순위 큐에 삽입
	const q = [[0, start]];

	while (q.length > 0) {
		const [dist, node] = q.shift();
		const currDist = dists[node];

		// 우선순위에서 나온 값이 저장되어 있는 값보다 적으면 아래의 로직 실행
		if (currDist < dist) continue;

		// 인접 정점까지의 거리가 기록된 거리보다 짧으면 거리값을 갱신하고
   		// 거리 값이 갱신된 정점들을 우선순위 큐에 넣는다
		const linkedNodes = graph.get(node);
		if (!!linkedNodes) {
			linkedNodes.forEach((a) => {
				const [linkedDist, linkedNode] = a;
				const sumDist = dist + linkedDist;

				if (dists[linkedNode] > sumDist) {
					dists[linkedNode] = sumDist;
					q.push([sumDist, linkedNode]);
					q.sort((a, b) => a[0] - b[0]);
				}
			});
		}
	}
}

 

---

예제문제

---

1. 백준 5719번 : 거의 최단 경로

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

5719번: 거의 최단 경로

 

 

문제해결 방법)
해당문제는 최단경로로 찾은 노드들을 제외하고 다시 최단거리를 찾아야 하는 문제이다.
1. 다익스트라 알고리즘으로 최단경로를 찾는다.
2. 찾은 최단 경로의 노드들을 메모이제이션한다. 
4. 다시 한번 다익스트라 알고리즘을 실행하는데 최단 경로의 노드들을 배제하며 찾는다.

 

먼저 예제로 주어진 노드들로 그래프를 만들자.

이때, 찾은 최단 경로의 노드들을 다시 확인해야 하므로 해당 그래프의 반대로 돌아오는 그래프도 만들어 주어야 한다.

예제 ) 
0 1 1
0 2 1
0 3 2
0 4 3
1 5 2
2 6 4
3 6 2
4 6 4
5 6 1

왼쪽 예제그래프, 오른쪽 reverse 예제그래프

Map을 이용해 그래프를 구현해 주었다. 

function setGraph(arr) {
	const g = new Map();
	const reverseG = new Map();

	arr.forEach((a) => {
		const [x, y, dist] = a.split(' ').map((b) => +b);

		if (!g.get(x)) {
			g.set(x, []);
		}

		if (!reverseG.get(y)) {
			reverseG.set(y, []);
		}

		g.get(x).push([dist, y]);
		reverseG.get(y).push([dist, x]);
	});

	return { g, reverseG };
}

아래와 같은 2개의 Map이 만들어진다. 

Map(6) {
  0 => [ [ 1, 1 ], [ 1, 2 ], [ 2, 3 ], [ 3, 4 ] ],
  1 => [ [ 2, 5 ] ],
  2 => [ [ 4, 6 ] ],
  3 => [ [ 2, 6 ] ],
  4 => [ [ 4, 6 ] ],
  5 => [ [ 1, 6 ] ]
} 

Map(6) {
  1 => [ [ 1, 0 ] ],
  2 => [ [ 1, 0 ] ],
  3 => [ [ 2, 0 ] ],
  4 => [ [ 3, 0 ] ],
  5 => [ [ 2, 1 ] ],
  6 => [ [ 4, 2 ], [ 2, 3 ], [ 4, 4 ], [ 1, 5 ] ]
}

 

두 개의 그래프 중에 예제그래프를 가지고 dijkstara 알고리즘을 실행한다.

dists라는 변수안에 최단거리 정보를 넣어준다. 

function dijkstra(start) {
	const queue = [];
	queue.push([0, start]);
	dists[start] = 0;

	while (queue.length > 0) {
		const [dist, node] = queue.shift();
		if (dists[node] < dist) continue;

		if (!!graph.get(node)) {
			graph.get(node).forEach((a) => {
				const cost = dist + a[0];

				if (dists[a[1]] > cost && !dropped[node][a[1]]) {
					dists[a[1]] = cost;
					queue.push([cost, a[1]]);
					// 우선순위큐를 만들기 위한 정렬 과정
					queue.sort((a, b) => a[0] - b[0]);
				}
			});
		}
	}
}

아래와 같이 최단거리 배열을 얻을 수 있다. 

dists  [0, 1, 1, 2, 3, 3, 4]

최단 거리를 얻는 2가지 방법이 있다.

그래프를 다시 보면 노드 6까지 최단거리 4로 가는 방법이 2가지가 있는 것을 볼 수 있다.

0 -> 1 -> 5 -> 6
0 -> 3 -> 6 

이 두 방법을 뺀 최단거리는

0 -> 2 -> 6

을 거쳐서 오면 이 문제의 답인 5가 된다. 

 

그럼, 최단거리 4로 오는 노드를 거치지 않도록 reveser 예제그래프를 가지고 최단거리를 만들었던 노드들을 찾아 

메모이제이션을 해준다. 

다음과 같이 이중배열을 만들어주고, false로 채워준다.

최단거리노드들을 반대로 찾아가며 지나갔던 노드들은 true로 값을 바꿔줄 것이다. 

dropped = Array.from({ length: N }, () => new Array(N).fill(false));

dropped  [
  [false, false, false, false, false, false, false],
  [false, false, false, false, false, false, false],
  [false, false, false, false, false, false, false],
  [false, false, false, false, false, false, false],
  [false, false, false, false, false, false, false],
  [false, false, false, false, false, false, false],
]

 

반대로 데이터를 찾아나갈 때는 우선순위큐를 사용하지 않아도 되니 BFS 알고리즘을 이용해찾아준다. 

function bfs(start, end) {
	// 끝노드를 넣어준다.
	const queue = [end];
	const visited = [];

	while (queue.length > 0) {
		const node = queue.shift();
		if (node === start) continue;

		// reverse 그래프를 확인해간다.
		// 이때, visited를 꼭 채크하자.
		// 안하면 시간초과 난다.
		if (!!reGraph.get(node) && !visited.includes(node)) {
			visited.push(node);
			reGraph.get(node).forEach((a) => {
				const [dist, prev] = a;
				const cost = dists[prev] + dist;
                
				// 이전 노드의 거리와 현재 거리를 더한 값이 나의 최단거리와 같다면
				// dropped 에 표시해주고,
				// 이전 노드를 queue에 넣어 탐색해나간다.
				if (dists[node] === cost) {
					dropped[prev][node] = true;
					queue.push(prev);
				}
			});
		}
	}
}

bfs 알고리즘을 실행하고 나면, 최단거리로 갈 수 있는 노드들의 길에 true로 표시 되어 있음을 볼 수 있다. 

dropped  [
  ## (0 -> 1)/(0 -> 3)	
  [ false, true, false, true, false, false, false],
  ## (1 -> 5)
  [ false, false, false, false, false, true, false],
  [ false, false, false, false, false, false, false],
  ## (3 -> 6)
  [ false, false, false, false, false, false, true],
  [ false, false, false, false, false, false, false],
  ## (5 -> 6)
  [ false, false, false, false, false, false, true],
  [ false, false, false, false, false, false, false]
]

 

이제 다익스트라 알고리즘을 다시 실행하면, 

최단거리 5를 찾아준다. 

 

전체 코드

---

const fs = require('fs');
const input = fs.readFileSync('./dev/stdin').toString().split('\n');

let graph = null;
let reGraph = null;
let dists = null;
let dropped = null;

function setGraph(arr) {
	const g = new Map();
	const reverseG = new Map();

	arr.forEach((a) => {
		const [x, y, dist] = a.split(' ').map((b) => +b);

		if (!g.get(x)) {
			g.set(x, []);
		}

		if (!reverseG.get(y)) {
			reverseG.set(y, []);
		}

		g.get(x).push([dist, y]);
		reverseG.get(y).push([dist, x]);
	});

	return { g, reverseG };
}

function dijkstra(start) {
	const queue = [];
	queue.push([0, start]);
	dists[start] = 0;

	while (queue.length > 0) {
		const [dist, node] = queue.shift();
		if (dists[node] < dist) continue;

		if (!!graph.get(node)) {
			graph.get(node).forEach((a) => {
				const cost = dist + a[0];

				if (dists[a[1]] > cost && !dropped[node][a[1]]) {
					dists[a[1]] = cost;
					queue.push([cost, a[1]]);
					queue.sort((a, b) => a[0] - b[0]);
				}
			});
		}
	}
}

function bfs(start, end) {
	const queue = [end];
	const visited = [];

	while (queue.length > 0) {
		const node = queue.shift();
		if (node === start) continue;

		if (!!reGraph.get(node) && !visited.includes(node)) {
			visited.push(node);
			reGraph.get(node).forEach((a) => {
				const [dist, prev] = a;
				const cost = dists[prev] + dist;
				if (dists[node] === cost) {
					dropped[prev][node] = true;
					queue.push(prev);
				}
			});
		}
	}
}

function solution(input) {
	while (input.length > 0) {
		let [N, M] = input
			.shift()
			.split(' ')
			.map((a) => +a);

		if (N === 0 && M === 0) break;

		let [S, E] = input
			.shift()
			.split(' ')
			.map((a) => +a);

		let params = input.splice(0, M);

		const { g, reverseG } = setGraph(params);
		graph = g;
		reGraph = reverseG;
		dists = Array(N).fill(Infinity);
		dropped = Array.from({ length: N }, () => new Array(N).fill(false));
		dijkstra(S);
		bfs(S, E);
		dists = Array(N).fill(Infinity);
		dijkstra(S);

		const result = dists[E] === Infinity ? -1 : dists[E];
		console.log(result);
	}
}

solution(input);