다익스트라 알고리즘으로 경로 나타내기
Dijkstra's Algorithm
특정한 두 노드 사이의 최단 거리를 구하는데 많이 사용되는 다익스트라 알고리즘은 네덜란드의 컴퓨터 과학자 에츠허르 다익스트라(Edsger W. Dijkstra)에 의해 만들어졌습니다. 다익스트라 알고리즘은 그래프 자료구조를 공부할 때 필수적으로 접하게 될만큼 중요도가 높은 알고리즘입니다. 그만큼 현실 세계의 많은 문제들을 해결하기 위해 사용되고 있는 것이지요. 그런데 이렇게 중요한 알고리즘이면서, 막상 공부할 때는 최단 거리를 구하는 코드를 제시합니다. 이런 아쉬움으로 인해 이번 기회에 다익스트라 알고리즘을 이용해 경로를 구하는 방법을 알아보려 합니다.
알고리즘의 전체적인 흐름은 다음과 같습니다.
- 알고리즘에 사용할 테이블(최단 거리, 부모, 방문 여부)을 만들고 초기화합니다.
- 현재 참조 중인 노드와 인접하면서, 아직 방문하지 않은 노드 중 거리가 가장 짧은 노드를 구합니다.
- 위에서 구한 노드를 통해 최단 거리, 부모, 방문 여부 테이블의 값을 갱신합니다.
두 번째와 세 번째의 과정을 반복하면서 모든 노드의 참조를 마치면 최단 경로와 거리를 알 수 있습니다 🙂
그래프 만들기
const graph = {
start: { A: 5, B: 2 },
A: { start: 1, C: 4, D: 2 },
B: { A: 8, D: 7 },
C: { D: 6, end: 3 },
D: { end: 1 },
end: {},
};
예제에서 사용할 그래프는 객체 형태로 만들었으며, 각 노드는 연결된 노드와 가중치(거리)를 담고 있습니다. 그래프를 보면 start와 A의 거리가 서로 다른 것을 확인하실 수 있는데, 이는 시작 지점을 변경했을 때의 결과를 다르게 보기 위함입니다.
최단 거리 노드 구하기
const findShortestNode = (distances, visited) => {
let shortest = null;
for (const node in distances) {
const isShortest = shortest === null || distances[node] < distances[shortest];
if (isShortest && !visited.includes(node)) {
shortest = node;
}
}
return shortest;
};
findShortestNode는 현재 참조 중인 노드로부터 아직 방문하지 않았고, 최단 거리가 제일 짧은 노드를 구하는 함수입니다. 매개변수로 받은 distances와 visited에 포함되어 있는 값은 현재 참조하고 있는 노드에 따라 값이 달라집니다. start 노드를 기준으로 경로를 구한다 하면 distances는 초기값으로 { end: MaxValue, A: 5, B: 2 }을 갖고 있으며, visited는 아직 방문을 완료한 노드가 없으므로 비어있습니다. 이어서 구현하는 다익스트라 알고리즘을 보면서 두 테이블이 어떻게 변화하는지 살펴보면 좋습니다.
테이블 생성
const dijkstra = (graph, startNode, endNode) => {
const distances = { ...{ endNode: Number.MAX_VALUE }, ...graph[startNode] };
const parents = { endNode: null };
for (const child in graph[startNode]) {
parents[child] = startNode;
}
const visited = [];
...
};
다익스트라 알고리즘에 사용되는 테이블은 총 세 가지입니다.
- distances: 현재 참조 중인 노드로부터 다른 노드까지의 최단 거리가 담길 테이블
- parents: 특정 노드로 가기 위해 거치게 되는 직전 노드를 담을 테이블 (이후 경로를 알 수 있도록)
- visited: 방문을 마친 노드를 담을 테이블 (이후 다시 참조하지 않도록)
다익스트라 알고리즘은 이렇게 세 가지 테이블을 갱신해나가는 식으로 문제를 해결합니다.
테이블 갱신
const dijkstra = (graph, startNode, endNode) => {
...
let node = findShortestNode(distances, visited);
while (node) {
const distance = distances[node];
const children = graph[node];
for (const child in children) {
if (String(startNode) === String(child)) continue;
else {
const cost = distance + children[child];
if (!distances[child] || distances[child] > cost) {
distances[child] = cost;
parents[child] = node;
}
}
}
visited.push(node);
node = findShortestNode(distances, visited);
}
...
}
이제 반복문을 통해 모든 노드의 방문을 마칠 때까지 순회하면서 앞서 만든 세 가지 테이블을 갱신합니다. 반복문 안에서 특정 노드로 가는 데 걸리는 비용을 비교하여 더 적은 값을 저장하게 됩니다. 예를 들어 start → A → B의 비용이 start → B보다 적게 든다면, B까지의 최단 거리는 A를 거쳐가는 비용이 되는 것입니다.
두 노드 사이의 최단 거리 & 경로 구하기
const dijkstra = (graph, startNode, endNode) => {
...
const shortestPath = [endNode];
let parent = parents[endNode];
while (parent) {
shortestPath.push(parent);
parent = parents[parent];
}
shortestPath.reverse();
return { distance: distances[endNode], path: shortestPath };
};
반복문을 통한 테이블 갱신이 완료되면, parents 테이블을 통해 목적지까지 거치게 된 경로를 얻을 수 있습니다. 목적지 노드인 endNode를 시작으로 부모 → 부모 → ... → 부모 형태로 노드를 참조해 나가면 됩니다. 그리고 이렇게 하면 경로가 역순으로 담기게 되므로, 마지막에는 reverse 메소드를 사용해 경로가 올바르게 보이도록 합니다.
여기까지 구현하면 알고리즘은 모두 만든 것이므로 함수를 호출해 결과를 확인하면 됩니다.
References 📝
'💻 컴퓨터공학 > 알고리즘' 카테고리의 다른 글
자바스크립트로 코딩 테스트 준비하기 (0) | 2022.02.22 |
---|---|
자바스크립트스럽게 퀵 정렬 구현하기 (0) | 2022.02.10 |
스택을 이용한 계산기 만들기 (0) | 2022.02.01 |
이진 탐색 (Binary Search) (0) | 2021.10.28 |
정렬 알고리즘 (Sorting Algorithms) (0) | 2021.10.27 |
댓글
이 글 공유하기
다른 글
-
자바스크립트로 코딩 테스트 준비하기
자바스크립트로 코딩 테스트 준비하기
2022.02.22 -
자바스크립트스럽게 퀵 정렬 구현하기
자바스크립트스럽게 퀵 정렬 구현하기
2022.02.10 -
스택을 이용한 계산기 만들기
스택을 이용한 계산기 만들기
2022.02.01 -
이진 탐색 (Binary Search)
이진 탐색 (Binary Search)
2021.10.28