我正在 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
}
}
最佳答案
正如 obourgain 指出的那样,代码的关键错误在于当两个节点未连接时将最小距离解释为 0。
如果两个节点断开连接,它们之间的最小距离应该是无穷,这是因为两个断开连接的节点的成本必须大于任何连接节点的成本,一个简单的修复您的代码是用 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
),代码注释为“更改#2”的是在断开连接时将两个节点之间的最小距离视为“无限”。
关于algorithm - Scala - 两个节点之间的最短路径递归算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40622358/