沐码小站

单源点正边权最短路径的经典求法。

let gragh = {
  A: {
    B: 1,
    C: 12
  },
  B: {
    C: 9,
    D: 3
  },
  C: {
    E: 5
  },
  D: {
    C: 4,
    E: 13,
    F: 15
  },
  E: {
    F: 4
  },
  F: {
    
  }
}

function nearestPath (gragh, from, to) {
  let dis = {}, paths = {}, visited = new Map()
  visited.set(from, 1)
  let num = 0
  for (let p in gragh) {
    num++
    if (p === from) {
      dis[p] = 0
    } else if (gragh[from][p]) {
      dis[p] = gragh[from][p]
      paths[p] = [from, p]
    } else {
      dis[p] = Infinity
      paths[p] = []
    }
  }
  while (visited.size < num) {
    let minKey
    for (let key in gragh) {
      if (key === from || visited.has(key)) continue
      if (minKey === undefined || dis[key] < dis[minKey]) {
        minKey = key
      }
    }
    if (minKey === to) break
    visited.set(minKey, 1)
    for (let p in gragh[minKey]) {
      console.log(paths)
      if (p === minKey) continue
      if (dis[p] > dis[minKey] + gragh[minKey][p]) {
        paths[p] = [...paths[minKey], p]
        dis[p] = dis[minKey] + gragh[minKey][p]
      }
    }
  }
  return paths[to]
}

console.log(nearestPath(gragh, 'A', 'C'))