Scala - 2つのノード間の最短経路再帰アルゴリズム

Question

私はScalaでDijkstraの最短経路アルゴリズムを再帰的に実装していますが、何か問題があります。私はノードに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で指摘されているように、2つのノードが接続されていない場合、コードの重大なエラーは最小距離を0と解釈することです。

それらが切断されている場合、2つのノード間の最小距離は、無限なければならない、2つの切断ノードのコストは、任意の接続されたノードのコストよりも大きくなければならないので、これは、あなたのコードへの1つの単純な修正がです無限を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"でコメントされたコードが2つのノード間のmin-distanceを切断すると「無限」として扱います。

Answer 2

エラーが最後の行にある：

if (pathLength.isEmpty) 0 else pathLength.min 

がpathLength.isEmpty場合、それは2つの点が接続されていないことを意味します。しかし、この関数は0を返します。