1type Graph = Record<string, Record<string, number>>;
2
3/** Возвращает имя непроработанного узла с наименьшей стоимостью или null */
4function lowestCostNode(costs: Record<string, number>, processed: Set<string>): string | null {
5  let lowest = Infinity;
6  let lowestNode: string | null = null;
7  for (const node in costs) {
8    const cost = costs[node];
9    if (cost < lowest && !processed.has(node)) {
10      lowest = cost;
11      lowestNode = node;
12    }
13  }
14  return lowestNode;
15}
16
17/**
18 * Дейкстра: кратчайшие пути от start до всех вершин (неотрицательные веса).
19 * Возвращает стоимость пути до finish и таблицу родителей для восстановления маршрута.
20 */
21function dijkstra(graph: Graph, start: string, finish: string) {
22  const costs: Record<string, number> = {};
23  const parents: Record<string, string | null | undefined> = {};
24  const processed = new Set<string>();
25
26  // Инициализация: стоимости соседей start, прочие = Infinity
27  for (const node in graph) {
28    if (node !== start) costs[node] = Infinity;
29  }
30  for (const n in (graph[start] ?? {})) {
31    costs[n] = graph[start][n];
32    parents[n] = start;
33  }
34  parents[start] = null;
35  if (parents[finish] === undefined) parents[finish] = null;
36
37  // Основной цикл
38  let node = lowestCostNode(costs, processed);
39  while (node) {
40    const cost = costs[node];
41    const neighbors = graph[node] ?? {};
42    for (const n in neighbors) {
43      const newCost = cost + neighbors[n];
44      if (costs[n] === undefined || newCost < costs[n]) {
45        costs[n] = newCost;
46        parents[n] = node;
47      }
48    }
49    processed.add(node);
50    node = lowestCostNode(costs, processed);
51  }
52
53  return { cost: costs[finish], parents };
54}
55
56/** Восстановление пути по таблице родителей */
57function pathFromParents(parents: Record<string, string | null | undefined>, finish: string): string[] {
58  const path: string[] = [finish];
59  let cur = parents[finish] ?? null;
60  while (cur) {
61    path.push(cur);
62    cur = parents[cur] ?? null;
63  }
64  return path.reverse();
65}
66
67/*** Пример из «Грокаем алгоритмы» ***/
68const graph: Graph = {
69  start: { a: 6, b: 2 },
70  a:     { fin: 1 },
71  b:     { a: 3, fin: 5 },
72  fin:   {}
73};
74
75const { cost, parents } = dijkstra(graph, 'start', 'fin');
76const path = pathFromParents(parents, 'fin');
77
78console.log('shortest cost:', cost);          // -> 6
79console.log('path:', path.join(' -> '));      // -> start -> b -> a -> fin
80