Dijkstra's algorithm

import heapq


def dijkstra(graph, start):
    dist = {start: 0}
    queue = [(0, start)]
    done = set()
    while queue:
        d, node = heapq.heappop(queue)
        if node in done:
            continue
        done.add(node)
        for nxt, weight in graph[node]:
            if nxt in done:
                continue
            nd = d + weight
            if nd >= dist.get(nxt, float("inf")):
                continue
            dist[nxt] = nd
            heapq.heappush(queue, (nd, nxt))
    return dist

function dijkstra(graph, start) {
  const dist = new Map([[start, 0]]);
  // [distance, node] pairs kept sorted: a simple stand-in for a priority queue.
  const queue = [[0, start]];
  const done = new Set();
  while (queue.length > 0) {
    const [d, node] = queue.shift();
    if (done.has(node)) continue;
    done.add(node);
    for (const [next, weight] of graph[node]) {
      if (done.has(next)) continue;
      const nd = d + weight;
      if (nd >= (dist.get(next) ?? Infinity)) continue;
      dist.set(next, nd);
      queue.push([nd, next]);
      queue.sort((x, y) => x[0] - y[0] || x[1] - y[1]);
    }
  }
  return dist;
}

import "container/heap"

type edge struct{ to, weight int }

type item struct{ dist, node int }

// pq is a min-heap of items, ordered by distance.
type pq []item

func (q pq) Len() int { return len(q) }
func (q pq) Less(i, j int) bool {
	return q[i].dist < q[j].dist || (q[i].dist == q[j].dist && q[i].node < q[j].node)
}
func (q pq) Swap(i, j int) { q[i], q[j] = q[j], q[i] }
func (q *pq) Push(x any)   { *q = append(*q, x.(item)) }
func (q *pq) Pop() any {
	old := *q
	x := old[len(old)-1]
	*q = old[:len(old)-1]
	return x
}

func dijkstra(graph [][]edge, start int) map[int]int {
	dist := map[int]int{start: 0}
	queue := &pq{{0, start}}
	done := map[int]bool{}
	for queue.Len() > 0 {
		cur := heap.Pop(queue).(item)
		if done[cur.node] {
			continue
		}
		done[cur.node] = true
		for _, e := range graph[cur.node] {
			if done[e.to] {
				continue
			}
			nd := cur.dist + e.weight
			if old, ok := dist[e.to]; ok && nd >= old {
				continue
			}
			dist[e.to] = nd
			heap.Push(queue, item{nd, e.to})
		}
	}
	return dist
}

use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap, HashSet};

fn dijkstra(graph: &[Vec<(usize, u32)>], start: usize) -> HashMap<usize, u32> {
    let mut dist = HashMap::from([(start, 0)]);
    let mut queue = BinaryHeap::from([Reverse((0, start))]);
    let mut done = HashSet::new();
    while let Some(Reverse((d, node))) = queue.pop() {
        if !done.insert(node) {
            continue;
        }
        for &(next, weight) in &graph[node] {
            if done.contains(&next) {
                continue;
            }
            let nd = d + weight;
            if nd >= *dist.get(&next).unwrap_or(&u32::MAX) {
                continue;
            }
            dist.insert(next, nd);
            queue.push(Reverse((nd, next)));
        }
    }
    dist
}