Dijkstra
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번 마을부터 각 마을까지의 최단 거리
}
dijkstra(
[
[1, 2, 1],
[1, 3, 2],
[2, 3, 2],
[3, 4, 3],
[3, 5, 2],
[3, 5, 3],
[5, 6, 1]
],
6
)
<img alt="image@1.png" src="${await FileAttachment("image@1.png").url()}">
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.