Dijkstra's Algorithm in Python, Java and TypeScript

import heapq
import math


def dijkstra(graph, source):
    distance = {vertex: math.inf for vertex in graph}
    parent = {vertex: None for vertex in graph}
    settled = set()
    distance[source] = 0
    queue = [(0, source)]
    while queue:
        _, vertex = heapq.heappop(queue)
        if vertex in settled:
            continue
        settled.add(vertex)
        for neighbour, weight in graph[vertex]:
            if neighbour in settled:
                continue
            if distance[vertex] + weight < distance[neighbour]:
                distance[neighbour] = distance[vertex] + weight
                parent[neighbour] = vertex
                heapq.heappush(queue, (distance[neighbour], neighbour))
    return distance, parent


def path_to(parent, target):
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]


GRAPH = {
    "A": [("B", 2), ("C", 7)],
    "B": [("C", 3), ("D", 8)],
    "C": [("D", 2), ("E", 6)],
    "D": [("E", 1)],
    "E": [],
}

distance, parent = dijkstra(GRAPH, "A")
for vertex in GRAPH:
    print(f"{vertex}: {distance[vertex]} via {parent[vertex] or '-'}")
print("path to E:", " -> ".join(path_to(parent, "E")))

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

public class DijkstraCode {
    record Edge(String to, int weight) {}

    record Entry(int distance, String vertex) {}

    record Result(Map<String, Integer> distance, Map<String, String> parent) {}

    static Result dijkstra(Map<String, List<Edge>> graph, String source) {
        Map<String, Integer> distance = new HashMap<>();
        Map<String, String> parent = new HashMap<>();
        Set<String> settled = new HashSet<>();
        PriorityQueue<Entry> queue = new PriorityQueue<>(Comparator.comparingInt(Entry::distance));
        distance.put(source, 0);
        queue.add(new Entry(0, source));
        while (!queue.isEmpty()) {
            String vertex = queue.poll().vertex();
            if (!settled.add(vertex)) continue;
            for (Edge edge : graph.get(vertex)) {
                if (settled.contains(edge.to())) continue;
                int candidate = distance.get(vertex) + edge.weight();
                if (candidate < distance.getOrDefault(edge.to(), Integer.MAX_VALUE)) {
                    distance.put(edge.to(), candidate);
                    parent.put(edge.to(), vertex);
                    queue.add(new Entry(candidate, edge.to()));
                }
            }
        }
        return new Result(distance, parent);
    }

    static List<String> pathTo(Map<String, String> parent, String target) {
        List<String> path = new ArrayList<>();
        for (String vertex = target; vertex != null; vertex = parent.get(vertex)) path.add(vertex);
        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {
        Map<String, List<Edge>> graph = new LinkedHashMap<>();
        graph.put("A", List.of(new Edge("B", 2), new Edge("C", 7)));
        graph.put("B", List.of(new Edge("C", 3), new Edge("D", 8)));
        graph.put("C", List.of(new Edge("D", 2), new Edge("E", 6)));
        graph.put("D", List.of(new Edge("E", 1)));
        graph.put("E", List.of());
        Result result = dijkstra(graph, "A");
        for (String vertex : graph.keySet()) {
            System.out.println(vertex + ": " + result.distance().get(vertex) + " via " + result.parent().getOrDefault(vertex, "-"));
        }
        System.out.println("path to E: " + String.join(" -> ", pathTo(result.parent(), "E")));
    }
}

type Edge = [string, number];

function dijkstra(graph: Map<string, Edge[]>, source: string): { distance: Map<string, number>; parent: Map<string, string> } {
  const distance = new Map<string, number>([...graph.keys()].map((v) => [v, Infinity]));
  const parent = new Map<string, string>();
  const settled = new Set<string>();
  distance.set(source, 0);
  while (settled.size < graph.size) {
    let vertex: string | null = null;
    for (const [candidate, d] of distance) {
      if (!settled.has(candidate) && d < Infinity && (vertex === null || d < distance.get(vertex)!)) vertex = candidate;
    }
    if (vertex === null) break;
    settled.add(vertex);
    for (const [neighbour, weight] of graph.get(vertex)!) {
      if (settled.has(neighbour)) continue;
      if (distance.get(vertex)! + weight < distance.get(neighbour)!) {
        distance.set(neighbour, distance.get(vertex)! + weight);
        parent.set(neighbour, vertex);
      }
    }
  }
  return { distance, parent };
}

function pathTo(parent: Map<string, string>, target: string): string[] {
  const path: string[] = [];
  for (let vertex: string | undefined = target; vertex !== undefined; vertex = parent.get(vertex)) path.push(vertex);
  return path.reverse();
}

const graph = new Map<string, Edge[]>([
  ["A", [["B", 2], ["C", 7]]],
  ["B", [["C", 3], ["D", 8]]],
  ["C", [["D", 2], ["E", 6]]],
  ["D", [["E", 1]]],
  ["E", []],
]);
const { distance, parent } = dijkstra(graph, "A");
for (const vertex of graph.keys()) console.log(`${vertex}: ${distance.get(vertex)} via ${parent.get(vertex) ?? "-"}`);
console.log(`path to E: ${pathTo(parent, "E").join(" -> ")}`);