Floyd-Warshall Shortest Path Algorithm Fehler

Question

Problem Statement: https://www.hackerrank.com/challenges/floyd-city-of-blinding-lights

Code:

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")) 
    } 
} 

Failing Testfall:

Eingang: https://paste.ubuntu.com/24406100/

Ausgang: https://paste.ubuntu.com/24406106/

Diese ist th Der Testfall fällt nur aus und ich bin nicht in der Lage, das Problem mit meinem Code herauszufinden.

EDIT: Fixed Code, wie @qwertyman wies darauf hin, kürzeste Pfade mit zwei oder Modus Kanten würde die Gewicht 351 überschreiten. Der richtige unendliche Wert für dieses Problem wäre, MaxEdgeWeight * MaxNodes-1 + 1 = 350 * (400-1) + 1.

Fest Code:

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

das Programm verwendet den Wert 351 als Marker für ungültige Abstände, die das Problem zu sein scheint.

Obwohl bekannt ist, dass das maximale Gewicht jeder Kante 350 beträgt, kann dennoch ein Abstand mit dem Wert 351 über einen aus zwei oder mehr Kanten bestehenden Pfad erreicht werden.