Dijkstra 算法寻找所有可能的最短路径

Question

我正在研究 Dijkstra 算法，我确实需要找到所有可能的最短路径，而不仅仅是一条。我使用邻接矩阵并应用 Dijkstra 算法，我可以找到最短路径。但我需要找到具有最小成本的所有路径，我的意思是所有可能的解决方案（如果存在）。

对于单一解决方案，这就是我的算法的工作原理：

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

如果您在这里以伪代码形式查看 Dijkstra 算法：
维基百科 Dijkstra 算法伪代码

您会注意到称为 Relax 的行。目前，它仅包含找到的路径小于当前最短路径的情况，但如果它们相等，则不会执行任何操作。您可能应该将所有同样短的路径保留在列表中。

Answer 2

如果您的 Dijkstra 算法的实现基于优先级队列，请采用您的第一个解决方案，记录深度并不断弹出解决方案，直到距离发生变化。

Answer 3

如果您的图表允许权重 = 0 的边并且还允许循环，请记住有无限多个最短路径，并且您不能希望将它们全部输出！

如果没有零权重边，或者您的图是 DAG，那么您的解决方案仍然存在问题：它要么不会根据需要生成所有最短路径，要么会使用O(2^N) 空间和时间复杂度。但是，也许可能有尽可能多的最短路径，所以你不能指望在一般情况下做得更好。

这是解决稍微更普遍的问题的最佳来源：查找k 最短路径 (Eppstein)。您可以通过迭代最短路径来应用此方法，并在比前一条路径长的第一条路径处停止。

对于仅找到（等效）最短路径的受限问题，Anderson Imes 上面的提示（这是家庭作业吗？否则应该有人拼写出来）很好，并且比上面简单得多。

Answer 4

我不太确定 Dijkstra 算法是否可以轻松适应这一点；当然，这并不像删除访问过的边那么简单，因为n个最短的可能共享其中的一些。

因此，一个近乎蛮力但启发式的解决方案是尝试这个：

• 对于最短路径中的每条边 E：
  • 删除 E 并在新图表上再次运行修改后的 Dijkstra
  • 如果最短路径比获得的第一条路径长，则停止
  • 否则，重复从新子图中递归地一次删除一条边

我的直觉告诉我它应该可以工作，复杂性的增加与第一个解决方案的长度（边数中的n）成正比......如果没有更多的最短路径，它应该在第一轮结束，如果它找到另一个，它会继续尝试 n-1 次。与原始算法相比，最坏情况下的复杂性增加估计非常糟糕（我猜是n！），但这也意味着有很多路径，所以这是一项需要完成的工作任何算法...

编辑：多思考一下，复杂性的增加可能会比第一个找到的路径的节点数的阶乘更大，因为第二个路径可能有更多的节点！所以我认为估计这种方法的复杂性非常困难，但它应该类似于有效解决方案的数量乘以路径中的平均节点数乘以节点数的平方（最后一个术语是未经修改的算法的原始复杂性）。

编辑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

Answer 5

JgraphT 的 FloydWarshallShortestPaths 类查找所有最短路径。根据上述评论，您正在寻找两个顶点之间的最短路径。您可能需要使用 getShortestPaths 方法，该方法将返回从一个顶点到所有其他顶点的所有最短路径。然后您可能想过滤您感兴趣的结果。

Answer 6

考虑这个算法： https://www.programmingalgorithms.com/algorithm/dijkstra's -算法/php/
最后有一个“< $distance[$v])”条件。如果我们将其更改为“<= ...”，它将给出所有现有的最短路径。

为了收集路径，我们可以放置

$this->paths[$v][] = $u;
也排在这里。
整个片段在这里： https://pastebin.com/gk2ymyWw

                if (!$this->known[$v] && $graph[$u][$v] && $this->distance[$u] != $this->INT_MAX && $this->distance[$u] + $graph[$u][$v] <= $this->distance[$v]) {
                    $this->distance[$v] = $this->distance[$u] + $graph[$u][$v];
                    $this->paths[$v][] = $u;
                }

Answer 7

这篇 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 8

我刚刚解决了一个任务，使用 Dijkstra 算法在 leetcode.com 上找到所有可能的最短路径。

唯一的区别是如何从“parents”和“distances”数组中提取信息。

主要思想是

• 您从目标移动到源，并从最佳路径（“父母”数组）中的每个节点移动，
• 您正在寻找与记录的父节点具有相同最小距离的邻居，然后
• 递归地移动所有节点那些可能的父母，直到你到达源头。

下面是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)