다익스트라 최단 경로 (Dijkstra Algorithm)
다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘입니다. 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾습니다. (단, 음의 간선이 없을 때만 정상 작동합니다)
각 노드에 대해 이전에 저장된 최단 거리와 현재 노드를 거쳐가는 거리를 비교하여 계속해서 최소값을 갱신해나가는 방식입니다.
const graph = {
A: { B: 2, C: 5 },
B: { C: 1, D: 3 },
C: { D: 6 },
D: {}
};
function dijkstra(graph, start) {
const distances = {};
for (let node in graph) distances[node] = Infinity;
distances[start] = 0;
const visited = new Set();
while (true) {
let currNode = null;
let shortestDistance = Infinity;
// 가장 가까운 미방문 노드 찾기
for (let node in distances) {
if (!visited.has(node) && distances[node] < shortestDistance) {
shortestDistance = distances[node];
currNode = node;
}
}
if (currNode === null) break;
visited.add(currNode);
console.log(`현재 노드 ${currNode} 방문. 최단 거리: ${shortestDistance}`);
// 인접 노드 거리 갱신
for (let neighbor in graph[currNode]) {
let distance = distances[currNode] + graph[currNode][neighbor];
if (distance < distances[neighbor]) {
distances[neighbor] = distance;
}
}
}
return distances;
}
console.log("최종 최단 거리:", dijkstra(graph, 'A'));