CODEWITHSUNDEEP
algorithmscalagraphdijkstrashortest-path
Teodorico Levoff
Teodorico Levoff

Reputation: 1659

Scala - Shortest Path Between Two Nodes Recursive Algorithm

I am implementing Dijkstra's shortest path algorithm recursivingly in Scala, but I am having some trouble. I am getting the incorrect output for nodes 3 to 2, called like this, shortestPath(3, 2, x, BitSet.empty). This outputs 6, but the correct answer should be 7. I cannot seem to figure out what's wrong with my code. 

var x = ListBuffer(ListBuffer(0, 2, 3, 4), 
                   ListBuffer(2, 0, 0, 0), 
                   ListBuffer(3, 0, 0, 0), 
                   ListBuffer(4, 0, 0, 0))

My code is here shown below.

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

Upvotes: 0

Views: 1666

Answers (2)

chiwangc
chiwangc

Reputation: 3577

As pointed out by obourgain, the critical error of the code is at interpreting the min-distance as 0 when two nodes are not connected.

The min-distance between two nodes should be infinity if they are disconnected, this is because the cost of two disconnected nodes must be greater than the cost of any connected nodes, and one simple fix to your code is to identify infinity with Int.MaxValue.

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

This modification will give the expected answer Int = 7 when invoking shortestPath(3, 2, x, new BitSet()).

The code commented with "change #1" is to prevent integer overflow when the destination node is not reachable by the neighbor node (thus the min-distance is Int.MaxValue), and the code commented with "change #2" is to treat the min-distance between two nodes as "infinite" when they are disconnected.

Upvotes: 2

obourgain
obourgain

Reputation: 9356

The error is on the last line: 

  if (pathLength.isEmpty) 0 else pathLength.min

If pathLength.isEmpty, it means the two points are not connected. However, the function returns 0, which is interpreted as a connection with weight 0.

Upvotes: 1

Related Questions