다익스트라 알고리즘은 시작점의 거리를 0으로 두고, 미확정 노드 가운데 거리가 가장 작은 노드를 고릅니다. 그 노드를 통해 이웃에 더 짧게 갈 수 있으면 거리 후보를 갱신합니다.
한 번 확정된 거리는 다시 바뀌지 않는데, 이 성질은 간선 가중치가 음수가 아닐 때 성립합니다. 음수 간선이 있으면 다른 알고리즘을 선택해야 합니다.
언제 쓰나
도로망이나 서비스 호출 비용처럼 음수가 없는 경로의 최소 비용을 찾을 때 씁니다.
다익스트라 최단 경로
Dijkstra shortest path
음수가 아닌 간선 가중치에서 현재 가장 짧은 후보를 확정합니다.
···
<div class="v"><header><b>DIJKSTRA</b><span id="state"></span></header><main><div class="route" id="route"></div><div class="dist" id="dist"></div></main><footer>relax neighbors, then settle</footer></div>.v{width:min(92vw,660px);height:min(86vh,310px);box-sizing:border-box;padding:clamp(9px,2.5vmin,18px);border:1px solid var(--line);border-radius:14px;background:var(--surface);display:flex;flex-direction:column;gap:7px;color:var(--fg);font:500 clamp(15px,4.5vmin,19px)/1.25 var(--font-sans, sans-serif)}.v header,.v footer{display:flex;justify-content:space-between;align-items:center;gap:8px;white-space:nowrap}.v header b{color:var(--accent);font-size:.9em}.v header span,.v footer{color:var(--muted);font-size:.82em}.v main{flex:1;min-height:0;position:relative;overflow:hidden}.v .mono{font-family:ui-monospace,SFMono-Regular,Consolas,monospace}.v .active{background:var(--accent)!important;color:var(--bg)!important;border-color:var(--accent)!important}.v .muted{opacity:.45} .route{height:57%;display:flex;justify-content:space-around;align-items:center}.route b{border:1px solid var(--line);border-radius:50%;width:31px;height:31px;display:grid;place-items:center}.route em{color:var(--muted);font-style:normal}.dist{text-align:center;font:600 .9em ui-monospace,monospace;color:var(--accent)}let n=0;const names=["A","B","C","D"],dist=[[0,"∞","∞","∞"],[0,2,5,"∞"],[0,2,3,6],[0,2,3,4]];function draw(){document.getElementById("route").innerHTML=names.map((x,i)=>"<b class=\""+(i===n?"active":i>n?"muted":"")+"\">"+x+"</b>"+(i<3?"<em>→</em>":"")).join("");document.getElementById("dist").textContent=names.map((x,i)=>x+":"+dist[n][i]).join(" ");document.getElementById("state").textContent="settle "+names[n];n=(n+1)%4}draw();setInterval(draw,1000)