Published
Edited
Dec 29, 2021
Insert cell
# Dijkstra
Insert cell
Insert cell
function dijkstra(graph, N) {
const heap = new MinHeap(); // 우선순위 큐(힙)
heap.push({ node: 1, cost: 0 }); // 1번 마을부터 시작

const dist = [...Array(N + 1)].map(() => Infinity); // 계산하기 편하도록 N+1 길이만큼 리스트 생성
dist[1] = 0; // 1번 마을은 무조건 거리가 0

while (!heap.isEmpty()) {
// heap이 비어있지 않다면
// cost가 가장 낮은 정점을 뽑는다.
const { node: current, cost: currentCost } = heap.pop();

for (const [src, dest, cost] of graph) {
// 루프를 돌며 시작점, 도착점, 비용을 꺼낸다
const nextCost = cost + currentCost; // 비용

// 양방향을 고려하여 작성
if (src === current && nextCost < dist[dest]) {
// src가 현재 선택된 정점이면서 목적지까지 더 저렴할 경우
dist[dest] = nextCost; // 거리를 갱신한다.
heap.push({ node: dest, cost: nextCost }); // push
} else if (dest == current && nextCost < dist[src]) {
// dest가 현재 선택된 정점이면서 목적지까지 더 저렴할 경우
dist[src] = nextCost; // 거리를 갱신한다.
heap.push({ node: src, cost: nextCost }); // push
}
}
}

return dist; // 1번 마을부터 각 마을까지의 최단 거리
}
Insert cell
dijkstra(
[
[1, 2, 1],
[1, 3, 2],
[2, 3, 2],
[3, 4, 3],
[3, 5, 2],
[3, 5, 3],
[5, 6, 1]
],
6
)
Insert cell
<img alt="image@1.png" src="${await FileAttachment("image@1.png").url()}">
Insert cell

Purpose-built for displays of data

Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
Learn more