스칼라 - 두 노드 사이의 최단 경로 재귀 알고리즘

Question

저는 스칼라에서 다이크 스트라의 최단 경로 알고리즘을 재귀 적으로 구현하고 있지만 약간의 문제가 있습니다. 노드 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 
     } 
    } 

Answer 1

obourgain으로 지적했듯이 코드의 치명적인 오류는 두 노드가 연결되어 있지 않을 때 min-distance를 0으로 해석하는 것입니다.

두 노드 사이의 최소 거리는 연결이 끊어지면 무한대이어야합니다. 두 개의 연결이 끊어진 노드의 비용이 연결된 노드의 비용보다 커야하고 코드에 간단한 수정이 필요하기 때문입니다. 무한대를 Int.MaxValue으로 식별하십시오. shortestPath(3, 2, x, new BitSet())를 호출 할 때

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

이 수정 예상되는 대답 Int = 7을 줄 것이다.

"change # 1"로 주석 된 코드는 이웃 노드가 목적지 노드에 도달 할 수 없을 때 (따라서 min-distance가 Int.MaxValue) 정수 오버플로를 방지하고 "change # 2"로 주석 처리 된 코드가 두 노드 사이의 최소 거리를 연결 해제 할 때 "무한"으로 처리합니다.

Answer 2

오류는 마지막 줄에 :

if (pathLength.isEmpty) 0 else pathLength.min 

pathLength.isEmpty가있는 경우,이 두 지점이 연결되어 있지 않은 것을 의미한다. 그러나이 함수는 0을 가진 연결로 해석합니다.