플로이드 - 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/

이를 th이다 e는 실패한 테스트 케이스 일 뿐이므로 코드에 대한 문제를 파악할 수 없습니다.

수정 : @qwertyman이 지적했듯이 고정 코드는 2 또는 모드 가장자리가있는 최단 경로가 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의 거리에 계속 도달 할 수 있습니다.