如何计算节点之间的最短路径？

Question

我的程序有以下变量输入数组，例如： [AB3, EC10]

可以是任意长度，第一到第二个字符分别是路线的起点和终点。后面的数字是第一个和第二个字符（节点）之间的距离。

如果你只能一步一步地从一个节点前进到另一个节点（要从 A 到 D，你必须走 AB、BC、 CD, ED) 节点之间的距离是可变的？

const routesInfo = ["AB5", "BC4", "CD8", "DC8", "DE6", "AD5", "CE2", "EB3", "AE7"]

  const stop1 = 'A',
  stop2 = 'B',
  stop3 = 'C',
  stop4 = '',
  stop5 = ''

  var trip1dist = 0,
    trip2dist = 0,
    trip3dist = 0,
    trip4dist = 0,
    dist = 0

  // for 3 stations
  if (stop1 && stop2 && stop3 && (!stop4) && (!stop5)) {
    var foundFirst = false,
    foundSecond = false
    for (var i = 0; i<routesInfo.length;i++) {
      var origin = routesInfo[i].charAt(0),
      destination = routesInfo[i].charAt(1)
      if (origin == stop1 && destination == stop2) {
        distance = routesInfo[i].charAt(2)
        trip1dist = distance
        foundFirst = true
      }
      if (origin == stop2 && destination == stop3) {
        distance = routesInfo[i].charAt(2)
        trip2dist = distance
        foundSecond = true
      }
    }
    // REFACTOR CHECKING FOR IMPOSSIBLE ROUTE
    if (foundFirst && !foundSecond) {
      console.log(null)
    }
    if (!foundFirst && foundSecond) {
      console.log(null)
    }
    if (!foundFirst && !foundSecond) {
      console.log(null)
    }
    var total = Number(trip1dist) + Number(trip2dist)
    console.log('The distance of the trip was: '+total)
  }

Answer 1

如果您事先知道起点和终点，则可以运行 Dijkstra 算法找到起点和终点之间的最短路径。 Dijkstra 算法是图中最短路径问题的著名解决方案。您可以阅读更多相关信息 here。此外，您可以很容易地找到它的实现。

如果你想知道任意两个给定点之间的最短距离，你应该看看 Floyd-Warshall 算法。您可以阅读更多相关信息 here。

如何计算节点之间的最短路径？

How to calculate shortest possible route between nodes?

javascript

graph-theory