Dijkstra

pick a language to open the code

import heapq


def dijkstra(start, goal, cost):
    distance = {start: 0}
    prev = {start: -1}
    heap = [(0, start)]
    while heap:
        far, cell = heapq.heappop(heap)
        if cell == goal:
            return path_to(prev, goal)
        if far > distance[cell]:
            continue
        for other in neighbors(cell):
            step = far + cost[other]
            if step < distance.get(other, float('inf')):
                distance[other] = step
                prev[other] = cell
                heapq.heappush(heap, (step, other))
    return []

function dijkstra(start, goal, cost) {
  const distance = new Map([[start, 0]]);
  const prev = new Map([[start, -1]]);
  const heap = new MinHeap();
  heap.push(start, 0);
  while (heap.size > 0) {
    const [cell, far] = heap.pop();
    if (cell === goal) return pathTo(prev, goal);
    if (far > distance.get(cell)) continue;
    for (const other of neighbors(cell)) {
      const step = far + cost[other];
      if (step >= (distance.get(other) ?? Infinity)) continue;
      distance.set(other, step);
      prev.set(other, cell);
      heap.push(other, step);
    }
  }
  return [];
}

int dijkstra(int start, int goal, int prev[], int distance[], int n,
             const int cost[], MinHeap* heap) {
    for (int i = 0; i < n; i++) { distance[i] = INT_MAX; prev[i] = -2; }
    distance[start] = 0;
    prev[start] = -1;
    heap_push(heap, start, 0);
    while (heap->size > 0) {
        int far = heap_top_key(heap);
        int cell = heap_pop(heap);
        if (cell == goal) return 1;
        if (far > distance[cell]) continue;
        for (int d = 0; d < 4; d++) {
            int other = neighbor(cell, d);
            if (other < 0) continue;
            int step = far + cost[other];
            if (step >= distance[other]) continue;
            distance[other] = step;
            prev[other] = cell;
            heap_push(heap, other, step);
        }
    }
    return 0;
}

std::vector<int> dijkstra(int start, int goal, const std::vector<int>& cost) {
    std::unordered_map<int, int> distance{{start, 0}};
    std::unordered_map<int, int> prev{{start, -1}};
    std::priority_queue<std::pair<int, int>,
                        std::vector<std::pair<int, int>>,
                        std::greater<>> heap;
    heap.push({0, start});
    while (!heap.empty()) {
        auto [far, cell] = heap.top();
        heap.pop();
        if (cell == goal) return path_to(prev, goal);
        if (far > distance[cell]) continue;
        for (int other : neighbors(cell)) {
            int step = far + cost[other];
            auto found = distance.find(other);
            if (found != distance.end() && step >= found->second) continue;
            distance[other] = step;
            prev[other] = cell;
            heap.push({step, other});
        }
    }
    return {};
}

static List<int> Dijkstra(int start, int goal, int[] cost) {
    var distance = new Dictionary<int, int> { [start] = 0 };
    var prev = new Dictionary<int, int> { [start] = -1 };
    var heap = new PriorityQueue<int, int>();
    heap.Enqueue(start, 0);
    while (heap.Count > 0) {
        heap.TryDequeue(out int cell, out int far);
        if (cell == goal) return PathTo(prev, goal);
        if (far > distance[cell]) continue;
        foreach (int other in Neighbors(cell)) {
            int step = far + cost[other];
            if (distance.TryGetValue(other, out int known) && step >= known) {
                continue;
            }
            distance[other] = step;
            prev[other] = cell;
            heap.Enqueue(other, step);
        }
    }
    return new List<int>();
}

static List<Integer> dijkstra(int start, int goal, int[] cost) {
    Map<Integer, Integer> distance = new HashMap<>();
    Map<Integer, Integer> prev = new HashMap<>();
    distance.put(start, 0);
    prev.put(start, -1);
    PriorityQueue<int[]> heap =
        new PriorityQueue<>(Comparator.comparingInt(entry -> entry[1]));
    heap.add(new int[] {start, 0});
    while (!heap.isEmpty()) {
        int[] top = heap.poll();
        int cell = top[0], far = top[1];
        if (cell == goal) return pathTo(prev, goal);
        if (far > distance.get(cell)) continue;
        for (int other : neighbors(cell)) {
            int step = far + cost[other];
            if (step >= distance.getOrDefault(other, Integer.MAX_VALUE)) {
                continue;
            }
            distance.put(other, step);
            prev.put(other, cell);
            heap.add(new int[] {other, step});
        }
    }
    return List.of();
}