16

我正在研究 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" );
}
4

8 回答 8

16

如果您在此处以伪代码形式查看 Dijkstra 算法： Wikipedia Dijkstra's Algorithm Pseudocode

您会注意到称为“放松”的线。现在它只包含找到的路径是否小于当前最短路径的情况，但如果它们相等则不做任何事情。您可能应该将所有同样短的路径保留在列表中。

于 2010-05-12T13:59:40.250 回答
4

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

于 2010-05-12T13:57:48.163 回答
3

如果你的图允许边weight = 0和环，请记住有无限多的最短路径，你不能指望把它们全部输出！

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

这是一个稍微更普遍的问题的最佳来源：Finding the k Shortest Paths (Eppstein)。您可以通过迭代最短路径来应用它，在比前一条更长的第一条路径处停止。

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

于 2010-05-25T16:11:22.670 回答
1

我不太确定 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

于 2010-05-12T14:09:53.970 回答
1

考虑这个算法：https ://www.programmingalgorithms.com/algorithm/dijkstra's-algorithm/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;
                }
于 2021-07-25T18:37:39.180 回答
1

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

于 2015-08-19T23:15:29.077 回答
0

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
于 2015-08-19T10:36:40.680 回答
0

我刚刚解决了一项任务，使用 Dijkstra 算法在 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)
于 2017-12-30T03:35:03.057 回答