最短路径与拓扑排序

// 运行环境：Node.js 14+
// 保存为 dsa-l16.js，执行：node dsa-l16.js
// 用简单数组当优先队列（演示用，生产用 MinHeap）
function dijkstra(graph, start) {
  const dist = {}                       // 起点到各点的最短距离
  for (const v in graph) dist[v] = Infinity
  dist[start] = 0
  const visited = new Set()
  while (visited.size < Object.keys(graph).length) {
    // 取未访问中距离最小的节点
    let u = null, best = Infinity
    for (const v in dist) if (!visited.has(v) && dist[v] < best) { best = dist[v]; u = v }
    if (u === null) break
    visited.add(u)
    for (const [v, w] of graph[u]) {      // 松弛：经 u 到 v 更近则更新
      if (dist[u] + w < dist[v]) dist[v] = dist[u] + w
    }
  }
  return dist
}
const g = { A: [['B', 4], ['C', 2]], B: [['D', 3]], C: [['B', 1], ['D', 5]], D: [] }
console.log(dijkstra(g, 'A')) // { A:0, B:3, C:2, D:6 }

// 拓扑排序（Kahn）：不断删"入度为 0"的节点
function topoSort(n, edges) {
  const indeg = new Array(n).fill(0)
  const adj = Array.from({ length: n }, () => [])
  for (const [u, v] of edges) { adj[u].push(v); indeg[v]++ }
  const q = []; for (let i = 0; i < n; i++) if (indeg[i] === 0) q.push(i)
  const res = []
  while (q.length) {
    const u = q.shift(); res.push(u)
    for (const v of adj[u]) if (--indeg[v] === 0) q.push(v)
  }
  return res.length === n ? res : [] // 有环则返回空
}
console.log(topoSort(4, [[0,1],[1,2],[2,3]])) // [0,1,2,3]