Scala - рекурсивный алгоритм кратчайшего пути между двумя узлами

Я рекурсивно реализую алгоритм кратчайшего пути Дейкстры в Scala, но у меня возникли некоторые проблемы. Я получаю неправильный вывод для узлов с 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
      }
    }

graph scala algorithm shortest-path dijkstra
person Teodorico Levoff    schedule 16.11.2016    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Как указано obourgain, критическая ошибка кода заключается в интерпретации минимального расстояния как 0, когда два узла не являются связаны.

Минимальное расстояние между двумя узлами должно быть бесконечностью, если они отключены, это связано с тем, что стоимость двух отключенных узлов должна быть больше, чем стоимость любых подключенных узлов, и одно простое исправление для вашего кода - отождествлять бесконечность с 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
    }
}

Эта модификация даст ожидаемый ответ Int = 7 при вызове shortestPath(3, 2, x, new BitSet()).

Код с комментарием «изменение №1» предназначен для предотвращения целочисленного переполнения, когда целевой узел недоступен для соседнего узла (таким образом, минимальное расстояние равно Int.MaxValue), а код с комментарием «изменение №2» предназначен для обработки минимального - расстояние между двумя узлами как «бесконечное», когда они отключены.

person chiwangc    schedule 17.11.2016
comment
Теперь я понимаю! Но представленный алгоритм или идея верна? - person Teodorico Levoff; 17.11.2016
comment
@TeodoricoLevoff Просто чтобы прояснить, вы пытаетесь спросить, правильный ли ваш код в поиске кратчайшего пути между двумя узлами или верен трюк для определения бесконечности с помощью Int.MaxValue? - person chiwangc; 17.11.2016
comment
Если код верен в поиске кратчайшего пути между двумя узлами. - person Teodorico Levoff; 17.11.2016
comment
@TeodoricoLevoff Вы правы, ваш код фиксирует факт minDist(x, y) = min{ minDist(x, z) + dist(z, y) | z is a neighbor of x}, а случаи, пропущенные проверкой BitSet, не дадут более короткий путь при посещении повторяющихся узлов. - person chiwangc; 17.11.2016

arrow_upward
1
arrow_downward

Ошибка находится в последней строке:

  if (pathLength.isEmpty) 0 else pathLength.min

Если pathLength.isEmpty, это означает, что две точки не соединены. Однако функция возвращает 0, что интерпретируется как связь с весом 0.

person obourgain    schedule 16.11.2016
comment
В этом есть смысл. Как вы посоветуете мне это исправить? Я думал, что использую отрицательное число, например -1, но это точно не сработает. - person Teodorico Levoff; 16.11.2016
comment
На самом деле, я считаю, что возвращение 0 является правильным, потому что это не влечет за собой никаких затрат. - person Teodorico Levoff; 16.11.2016