Алгоритм Дейкстры, чтобы найти все кратчайшие возможные пути

Question

Я работаю над алгоритмом Дейкстры, и мне действительно нужно найти все возможные кратчайшие пути, а не только один. Я использую матрицу смежности и применил алгоритм Дейкстры, и я могу найти кратчайший путь. Но мне нужно найти все пути с такой минимальной стоимостью, я имею в виду все возможные решения, если они существуют.

Вот как работает мой алгоритм для одного решения:

public void dijkstra( int graph[][] )
{
    int d[] = new int[ graph.length ];
    int dC[] = new int[ graph.length ];
    int p[] = new int[ graph.length ];

    for( int i = 0; i < graph.length; i++ ){
        d[ i ] = 100; dC[ i ] = 100; p[ i ] = -1;
    }
    d[ 0 ] = 0; dC[ 0 ] = 0;

    int i = 0, min = 200, pos = 0; //You can change the min to 1000 to make it the largest number
    while( i < graph.length ){
        //extract minimum
        for( int j = 0; j < dC.length; j++ ){
            if( min > d[ j ] && dC[ j ] != -1 ){
                min = d[ j ]; pos = j;
            }
        }
        dC[ pos ] = -1;

        //relax
        for( int j = 0; j < graph.length; j++ ){
            if( d[ j ] > graph[ pos ][ j ] + d[ pos ] ){
                d[ j ] = graph[ pos ][ j ] + d[ pos ];
                p[ j ] = pos;
            }
        }
        i++; min = 200;
    }

    for( int j = 0; j < p.length; j++ ){
        System.out.print( p[ j ] + " " );
    }
    System.out.print( "\n" );
    for( int j = 0; j < d.length; j++ ){
        System.out.print( d[ j ] + " " );
    }
    System.out.print( "\n" );
}

Answer 1

Если вы посмотрите на алгоритм Дейкстры в форме псевдокода здесь: Псевдокод алгоритма Дейкстры из Википедии

Вы заметите линию, называемую Relax. Сейчас он содержит только случай, если найденный путь меньше текущего кратчайшего пути, но ничего не делается, если они равны . Вероятно, вы должны хранить все одинаково короткие пути в списке.

Answer 2

Если ваши графики допускают ребра с weight = 0, а также допускают циклы, помните, что существует бесконечно много кратчайших путей, и вы не можете надеяться вывести их все!

Если ребер с нулевым весом либо нет, либо ваш график является DAG, то ваше решение все еще проблематично: оно либо не создает всех кратчайших путей, сколько требуется, либо делает это с O(2^N) Пространственно-временная сложность. Но тогда, возможно, может быть как можно больше кратчайших путей, поэтому вы не можете надеяться на улучшение в общем случае.

Это лучший источник для более общей проблемы: Нахождение k кратчайших путей (Эппштейн). Вы можете применить это, перебирая кратчайшие пути, останавливаясь на первом пути, который длиннее предыдущего.

Для ограниченной задачи поиска только (эквивалентных) кратчайших путей подсказка Андерсона Имеса выше (это домашняя работа? В противном случае кто-то должен разобрать ее) хороша и намного проще, чем выше.

Answer 3

Если ваша реализация алгоритма Дейкстры основана на приоритетной очереди, возьмите ваше первое решение, запишите глубину и продолжайте выдавать решения, пока глубина не изменится.

Answer 4

Я только что решил задачу найти все возможные кратчайшие пути на leetcode.com, используя алгоритм Дейкстры.

Единственное отличие состоит в том, как вы извлекаете информацию из массивов "родители" и "расстояния".

Основная идея

• вы перемещаетесь от цели к источнику и от каждого узла в вашем оптимальном пути (массив «родителей»),
• вы ищете соседей, у которых было такое же минимальное расстояние до источника, как у зарегистрированного родителя, и
• затем рекурсивно перемещаясь по всем возможным родителям, пока вы не достигнете источника.

Ниже приведен код на Python.

if parent[endNode] > -1: # -1 means no path at all
            self.traversingAllNodes(parents, shortestDistances, endNode, [endNode])
    return self.finalList

def traversingAllNodes(self, parents, distances, startNode, path):
    if parents[startNode] == -1:
        self.saveFound(path) # saving one path
        return
    currentNode = startNode
    parent = parents[currentNode] # recorded parent
    optimalDistance = distances[parent] # distance from parent to source
    for node in self.graph[currentNode]: # moving via neighbords
        if distances[node] == optimalDistance: 
            path.append(node)
            self.traversingAllNodes(parents, distances, node, path)
            path.remove(node)

Answer 5

FloydWarshallShortestPaths класс JgraphT находит все кратчайшие пути. Основываясь на комментариях выше, вы ищете кратчайшие пути между двумя вершинами. Возможно, вы захотите использовать метод getShortestPaths , который будет возвращать все кратчайшие пути из вершины во все остальные вершины. Тогда вы можете отфильтровать интересующий вас результат.

Answer 6

В этой статье 1982 г. описан алгоритм для графов с многомерными весами ребер, который дает все кратчайшие пути.

Алгоритм отлично работает с простыми взвешенными графиками, поэтому должен работать для вашего случая.

Автор сравнивает его с Dijkstra, как в том, как он работает, так и в сравнении сложности во время выполнения.

В псевдокоде, перефразируя бумагу:

1. H is a heap of paths sorted on the weights of these paths, either
     a. lexicographically and decreasing in each element of the weight vector
     b. on the negative sum of all the elements in the weight vector
   Initially, H contains only path p0 (the starting point) the weight of which is O.
2. S1 through Sv are sets associated with vertices v1 through vv respectively.
   These sets contain the maximal paths to each vertex, as they are discovered.
   Initially, all sets are empty.
3. a. While (H is not empty) do begin
   b.   remove the root of H, p;
   c.   if p is not dominated by any of the paths in Sn where vn is last vertex of p
   d.     add it to Sn (the set of maxima for vertex vn)
   e.     for each possible extensions q of path p
   g.       if path q to node vm is not yet dominated by the maxima in Sm
   h.         insert q into H

Answer 7

Я не очень уверен, что алгоритм Дейкстры можно легко адаптировать для этого; Конечно, это не так просто, как удалить посещенные ребра, потому что n кратчайших может поделиться некоторыми из них.

Итак, почти грубое, но эвристически ориентированное решение - попробовать это:

• для каждого ребра E в кратчайшем пути:
  • удалите E и снова запустите модифицированную Дейкстру над новым графиком
  • если кратчайший путь длиннее первого полученного, остановите
  • иначе, повторите рекурсивное удаление по одному ребру за раз из нового подграфа

Моя интуиция подсказывает мне, что она должна работать с увеличением сложности, пропорциональным длине (n числа ребер) первого решения ... Если больше нет кратчайшего пути, оно должно заканчиваться на первый раунд, если он находит другой, он продолжается с n-1 попытками. Оценка увеличения сложности в наихудшем случае по сравнению с исходным алгоритмом очень плохая (n! Я полагаю?), Но это также означает, что существует множество путей, поэтому эту работу необходимо выполнить с любым алгоритмом ...

edit: Если подумать немного больше, увеличение сложности может быть даже больше, чем факториал числа узлов первого найденного пути, поскольку у второго может быть даже больше узлов! Поэтому я думаю, что очень сложно оценить сложность этого метода, но это должно быть что-то вроде числа допустимых решений, умноженного на среднее число узлов в путях, умноженное на число узлов в квадрате (это последний член исходная сложность неизмененного алгоритма).

edit 2: Я нашел исследовательскую работу по этому вопросу, для получения полного текста требуется подписка, но, возможно, вы найдете ее где-нибудь еще: http://ieeexplore.ieee.org/Xplore/login.jsp?reload=true&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F7719%2F21161%2F00982778.pdf%3Farnumber%3D982778&authDecision=-201