带优先队列的 Dijkstra 最短路

功能说明

该示例在邻接表表示的加权图上执行 Dijkstra 算法，计算从单一源点到所有可达节点的最短距离，并支持按目标节点回溯完整路径。它适合路网、依赖成本、服务调用延迟等非负权重场景。不可达节点不会出现在距离表中，pathTo 返回空数组。

关键代码

距离表初始只包含源点 0，previous 记录每个节点被松弛时的前驱。开放集合用数组实现二叉最小堆，push 上浮、pop 下沉，每次取出距离最小的节点。若节点已经结算则跳过，随后遍历其出边，遇到负权或非有限权重立即抛错。若新距离小于已知距离则更新距离、前驱并压入堆。pathTo 从目标沿 previous 回溯再反转。

使用注意

Dijkstra 要求所有边权非负，出现负权必须改用 Bellman-Ford。图使用 Map 表示，邻居可以不出现在键集合中，此时视为没有出边。堆中可能同时存在同一节点的旧条目，依靠 settled 集合去重。算法复杂度约为 O((V + E) log V)，超大图应关注 Map 与堆的内存占用。返回的距离表是只读视图，但内部 Map 仍可被调用方遍历。

验证方式

构造 a 到 d 的图，断言距离为 5 且路径为 a、b、c、d。测试不可达目标返回空数组、源点到自身路径只含源点。加入负权边断言 RangeError，源点不存在也断言 RangeError。再构造多条等价路径，确认返回其中一条合法最短路。

代码示例

export type WeightedGraph = ReadonlyMap<string, ReadonlyArray<readonly [string, number]>>;

interface HeapEntry {
  readonly node: string;
  readonly distance: number;
}

export interface ShortestPaths {
  readonly distances: ReadonlyMap<string, number>;
  pathTo(target: string): string[];
}

export function shortestPaths(graph: WeightedGraph, source: string): ShortestPaths {
  if (!(graph instanceof Map)) throw new TypeError("graph must be a Map");
  if (!graph.has(source)) throw new RangeError(`unknown source "${source}"`);

  const distances = new Map<string, number>([[source, 0]]);
  const previous = new Map<string, string>();
  const heap: HeapEntry[] = [{ node: source, distance: 0 }];
  const settled = new Set<string>();

  while (heap.length > 0) {
    const current = pop(heap);
    if (current === undefined) break;
    if (settled.has(current.node)) continue;
    settled.add(current.node);

    const edges = graph.get(current.node);
    if (edges === undefined) continue;
    for (const [neighbor, weight] of edges) {
      if (!Number.isFinite(weight) || weight < 0) {
        throw new RangeError(`edge "${current.node}" -> "${neighbor}" has an invalid weight`);
      }
      const candidate = current.distance + weight;
      const known = distances.get(neighbor);
      if (known === undefined || candidate < known) {
        distances.set(neighbor, candidate);
        previous.set(neighbor, current.node);
        push(heap, { node: neighbor, distance: candidate });
      }
    }
  }

  return {
    distances,
    pathTo(target: string): string[] {
      if (!distances.has(target)) return [];
      const path: string[] = [];
      let cursor: string | undefined = target;
      while (cursor !== undefined) {
        path.push(cursor);
        cursor = previous.get(cursor);
      }
      return path.reverse();
    },
  };
}

function push(heap: HeapEntry[], entry: HeapEntry): void {
  let index = heap.length;
  heap.push(entry);
  while (index > 0) {
    const parent = (index - 1) >> 1;
    const parentEntry = heap[parent];
    if (parentEntry === undefined || parentEntry.distance <= entry.distance) break;
    heap[index] = parentEntry;
    index = parent;
  }
  heap[index] = entry;
}

function pop(heap: HeapEntry[]): HeapEntry | undefined {
  const first = heap[0];
  const last = heap.pop();
  if (first === undefined || last === undefined || heap.length === 0) return first;
  let index = 0;
  while (true) {
    const left = index * 2 + 1;
    const right = left + 1;
    let smallest = index;
    let smallestEntry = last;
    const leftEntry = heap[left];
    if (leftEntry !== undefined && leftEntry.distance < smallestEntry.distance) {
      smallest = left;
      smallestEntry = leftEntry;
    }
    const rightEntry = heap[right];
    if (rightEntry !== undefined && rightEntry.distance < smallestEntry.distance) {
      smallest = right;
      smallestEntry = rightEntry;
    }
    if (smallest === index) break;
    heap[index] = smallestEntry;
    index = smallest;
  }
  heap[index] = last;
  return first;
}

const graph: WeightedGraph = new Map([
  ["a", [["b", 2], ["c", 5]]],
  ["b", [["c", 1], ["d", 7]]],
  ["c", [["d", 2]]],
  ["d", []],
]);
const result = shortestPaths(graph, "a");
console.log([...result.distances.entries()]);
console.log(result.pathTo("d"));
console.log(result.pathTo("missing"));