弗洛伊德 - 沃肖爾最短路徑算法錯誤

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/

這是th只有失敗的測試用例，我無法弄清楚我的代碼存在問題。

編輯：固定代碼，正如@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的距離。