Scala

Question

我正在 Scala 中递归地实现 Dijkstra 的最短路径算法，但我遇到了一些麻烦。我得到的节点 3 到 2 的输出不正确，这样调用 shortestPath(3, 2, x, BitSet.empty)。这输出 6，但正确答案应该是 7。我似乎无法弄清楚我的代码有什么问题。

var x = ListBuffer(ListBuffer(0, 2, 3, 4), 
                   ListBuffer(2, 0, 0, 0), 
                   ListBuffer(3, 0, 0, 0), 
                   ListBuffer(4, 0, 0, 0))

我的代码如下所示。

def shortestPath(cur: Int, dest: Int, graph: ListBuffer[ListBuffer[Int]], visited: BitSet) :Int = {
    val newVisited = visited + cur
    if(cur == dest) 0
    else {
      var pathLength = for(i <- graph(cur).indices; if(!visited(i) && graph(cur)(i) > 0)) yield {
          graph(cur)(i) + shortestPath(i, dest, graph, newVisited)
        }
      if (pathLength.isEmpty) 0 else pathLength.min
      }
    }

Answer 1

错误在最后一行：

  if (pathLength.isEmpty) 0 else pathLength.min

如果pathLength.isEmpty，表示两点不相连。但是，函数returns0，被解释为权重为0的连接。

Answer 2

正如 obourgain 所指出的，代码的关键错误在于当两个节点未连接时将最小距离解释为 0。

两个节点之间的最小距离应该是 infinity 如果它们是断开的，这是因为两个断开节点的成本必须大于任何连接节点的成本，对代码的一个简单修复是用 Int.MaxValue.

识别无穷大

def shortestPath(cur: Int, dest: Int, graph: ListBuffer[ListBuffer[Int]], visited: BitSet) :Int = {
    val newVisited = visited + cur
    if(cur == dest) 0
    else {
        var pathLength = for(i <- graph(cur).indices; if(!visited(i) && graph(cur)(i) > 0)) yield {
            val sLen = shortestPath(i, dest, graph, newVisited)
            if (graph(cur)(i) > Int.MaxValue - sLen) Int.MaxValue else graph(cur)(i) + sLen // change #1
        }
        if (pathLength.isEmpty) Int.MaxValue else pathLength.min // change #2
    }
}

此修改将在调用 shortestPath(3, 2, x, new BitSet()) 时给出预期的答案 Int = 7。

注释"change #1"的代码是为了在邻居节点不可达目标节点时防止整数溢出（因此最小距离为Int.MaxValue），注释"change #2"是将两个节点之间的min-distance视为断开连接时的"infinite"。

Scala - 两个节点之间的最短路径递归算法

Scala - Shortest Path Between Two Nodes Recursive Algorithm

algorithm

graph

dijkstra

shortest-path