Floyd-Warshall 最短路径算法错误

Question

问题陈述：https://www.hackerrank.com/challenges/floyd-city-of-blinding-lights

代码：

import scala.io.StdIn._
import scala.collection.mutable
object Solution {
    def FloydWarshall(n: Int, adj: Array[Array[Int]]): Array[Array[Int]] = {
        val distance: Array[Array[Int]] = adj
        for(k <- 0 until n){
            for(u <- 0 until n){
                for(v <- 0 until n){
                    distance(u)(v) = minimum(distance(u)(v), distance(u)(k) + distance(k)(v))
                }
            }
        }
        distance
    }

    def minimum(a: Int, b: Int):Int = {
        if(a < b){
            a
        } else {
            b
        }
    }

    def main(args: Array[String]) {
        var input: Array[Int] = readLine().split(" ").map(_.toInt)
        val n: Int = input(0)
        val m: Int = input(1)    
        val adj: Array[Array[Int]] = Array.fill(n, n)(351)

        for(_ <- 1 to m){
            input = readLine().split(" ").map(_.toInt)
            val u: Int = input(0)
            val v: Int = input(1)
            val w: Int = input(2)
            adj(u-1)(v-1) = w
        }

        for(i <- 0 until n){
            adj(i)(i) = 0
        }

        val q: Int = readInt()
        val distance: Array[Array[Int]] = FloydWarshall(n, adj)
        val results: mutable.ListBuffer[Int] = mutable.ListBuffer[Int]()
        for(_ <- 1 to q) {
            input = readLine().split(" ").map(_.toInt)
            val u: Int = input(0)
            val v: Int = input(1)
            val result: Int = if(distance(u-1)(v-1) == 351) -1 else distance(u-1)(v-1)    
            results += result
        }
        println(results.mkString("\n"))
    }
}

失败的测试用例：

输入：https://paste.ubuntu.com/24406100/

输出：https://paste.ubuntu.com/24406106/

这是唯一失败的测试用例，我无法找出我的代码的问题。

编辑：固定代码，正如@qwertyman 指出的那样，具有两个或模式边的最短路径将超过权重 351。此问题的正确无限值是 MaxEdgeWeight * MaxNodes-1 + 1 = 350 * (400-1) + 1.

固定代码：

import scala.io.StdIn._
import scala.collection.mutable
import util.control.Breaks._
object Solution {
    def FloydWarshall(n: Int, adj: Array[Array[Int]]): Array[Array[Int]] = {
        val distance: Array[Array[Int]] = adj
        for(k <- 0 until n){
            for(u <- 0 until n){
                for(v <- 0 until n){
                        distance(u)(v) = minimum(distance(u)(v), distance(u)(k) + distance(k)(v))    
                }
            }
        }
        distance
    }

    def minimum(a: Int, b: Int):Int = {
        if(a < b){
            a
        } else {
            b
        }
    }

    def main(args: Array[String]) {
        var input: Array[Int] = readLine().split(" ").map(_.toInt)
        val n: Int = input(0)
        val m: Int = input(1)
        val infinity: Int = 350 * 399 + 1// maximum shortest path N-1 edges
        val adj: Array[Array[Int]] = Array.fill(n, n)(infinity)

        for(_ <- 1 to m){
            input = readLine().split(" ").map(_.toInt)
            val u: Int = input(0) - 1
            val v: Int = input(1) - 1
            val w: Int = input(2)
            adj(u)(v) = w
        }

        for(i <- 0 until n){
            adj(i)(i) = 0
        }

        val q: Int = readInt()
        val distance: Array[Array[Int]] = FloydWarshall(n, adj)
        val results: mutable.ListBuffer[Int] = mutable.ListBuffer[Int]()
        for(_ <- 1 to q) {
            input = readLine().split(" ").map(_.toInt)
            val u: Int = input(0) - 1 
            val v: Int = input(1) - 1
            val result: Int = if(distance(u)(v) == infinity) -1 else distance(u)(v)
            results += result
        }
        println(results.mkString("\n"))
    }
}

Answer 1

程序使用值 351 作为无效距离的标记，这似乎是问题所在。

虽然已知每条边的最大权重为350，但是，通过由两条或更多条边组成的路径，仍然可以达到值为351的距离。

Floyd-Warshall 最短路径算法错误

Floyd-Warshall Shortest Path Algorithm Error

algorithm

scala

floyd-warshall