标签: floyd-warshall

我正在阅读Dijkstra的算法和Floyd-Warshall算法.据我所知,Dijkstra找到了从一个节点到所有其他节点的最佳路径,Floyd-Warshall找到了所有节点配对的最佳路径.

我的问题是,如果我在每个节点上运行它,Dijkstra算法比Floyd更有效,以便找到所有配对之间的最佳路径.

Dijkstra的运行时间是O(E + VlogV),其中Floyd是O(V ³).如果Dijkstra失败了,在这种情况下它的运行时间是什么？谢谢!

我一直在研究这三个,我在下面陈述我的推论.有人能告诉我,我是否已经足够准确地理解它们了吗？谢谢.

1. Dijkstra的算法仅在您拥有单个源并且您想知道从一个节点到另一个节点的最小路径时使用,但在这种情况下失败

2. 当任何所有节点都可以作为源时,使用Floyd-Warshall的算法,因此您希望最短距离从任何源节点到达任何目标节点.只有在出现负循环时才会失败

(这是最重要的一个.我的意思是,这是我最不确定的:)

3.Bellman-Ford像Dijkstra一样使用,当时只有一个来源.这可以处理负重量,它的工作方式与Floyd-Warshall相同,除了一个来源,对吗？

如果你需要看看,相应的算法是(礼貌的维基百科):

贝尔曼 - 福特:

 procedure BellmanFord(list vertices, list edges, vertex source)
   // This implementation takes in a graph, represented as lists of vertices
   // and edges, and modifies the vertices so that their distance and
   // predecessor attributes store the shortest paths.

   // Step 1: initialize graph
   for each vertex v in vertices:
       if v is source then v.distance := 0
       else v.distance := infinity
       v.predecessor := null

   // Step 2: relax …

我实现了弗洛伊德-沃肖尔返回每对节点/顶点和一之间的最短路径的距离,单这些对之间的最短路径.

是否有任何方法可以让它返回每条最短路径,即使有多条路径都是最短路径,对于每对节点？(我只是想知道我是否在浪费时间去尝试)

我需要通过无向图找到最短路径,其节点是实数(正和负)加权.这些权重就像您可以通过输入节点获得或松散的资源.

路径的总成本(资源总和)不是很重要,但必须大于0,并且长度必须尽可能短.

例如,考虑如下图:

A-start node; D-end node

A(+10)--B( 0 )--C(-5 )
     \     |    /
       \   |  /
D(-5 )--E(-5 )--F(+10)

最短的路径是AEFED

Dijkstra的算法本身并不起作用,因为它无法处理负值.所以,我想了几个解决方案:

首先使用Dijkstra算法计算从每个节点到出口节点的最短路径的长度,而不考虑权重.这可以像A*中的某种启发式值一样使用.我不确定这个解决方案是否可行,而且成本也很高.我也想过实现Floyd-Warshall的算法,但我不确定如何.

另一种解决方案是计算与Dijkstra算法不考虑权重的最短路径,如果计算路径的资源总和后,是小于零,经过的每个节点找到可能会很快增加资源和邻近节点,并将其添加到路径(如果需要,可以多次).如果有一个节点足以增加资源总和,但距计算的最短路径更远,则此解决方案将不起作用.

例如:

A- start node; E- end node
A(+10)--B(-5 )--C(+40)
      \
        D(-5 )--E(-5 )

你能帮我解决这个问题吗？

编辑:如果在计算最短路径时,您到达资源总和等于零的点,该路径无效,因为如果没有更多的汽油则无法继续.

我已经实现了Floyd Warshall算法并且它可以工作,但问题是我不知道如何找到所有未定义的路径.我在网上搜索过,但我只能找到如何检测图表是否有负循环的答案.

vector< vector <int> > floyd_warshall(vector< vector<int> > d, int n){
    for(int i = 0; i < n; i++) d[i][i] = 0;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < n; k++){
                if(d[j][i] + d[i][k] < d[j][k] and d[j][i] != INF and d[i][k] != INF){
                    d[j][k] = d[j][i] + d[i][k];
                }
            }
        }
    }

    return d;
}

在图表上运行算法后:

from: to:   weight:
0     1      1
1 …

我想在Haskell中使用Vectors 编写Floyd-Warshall所有对最短路径算法的有效实现,以期获得良好的性能.

实现非常简单,但不使用三维| V |×| V |×| V | 矩阵,使用二维向量,因为我们只读过前一个k值.

因此,该算法实际上只是传递2D矢量的一系列步骤,并且生成新的2D​​矢量.最终的2D矢量包含所有节点(i,j)之间的最短路径.

我的直觉告诉我,确保在每个步骤之前评估先前的2D向量是很重要的,所以我使用了函数BangPatterns的prev参数fw和严格foldl':

{-# Language BangPatterns #-}

import           Control.DeepSeq
import           Control.Monad       (forM_)
import           Data.List           (foldl')
import qualified Data.Map.Strict     as M
import           Data.Vector         (Vector, (!), (//))
import qualified Data.Vector         as V
import qualified Data.Vector.Mutable as V hiding (length, replicate, take)

type Graph = Vector (M.Map Int Double)
type TwoDVector = Vector (Vector Double)

infinity :: Double
infinity = 1/0

-- …

我阅读了维基百科给出的方法,通过修改Floyd Warshall算法在图表中打印两个给定点的短路径.我编写了这个,但它并没有真正给出预期的输出:

1. minimumDistanceMatrix[i][j]将图中各个权重的所有元素和矩阵中的所有元素初始化shortestPathCalculatorMatrix [i][j]为-1.

2. 然后 :

   // Find shortest path using Floyd–Warshall algorithm
   
   for ( unsigned int k = 0 ; k < getTotalNumberOfCities() ; ++ k)
      for ( unsigned int i = 0 ; i < getTotalNumberOfCities() ; ++ i)
         for ( unsigned int j = 0 ; j < getTotalNumberOfCities() ; ++ j)
             if ( minimumDistanceMatrix[i][k] + minimumDistanceMatrix[k][j] < minimumDistanceMatrix[i][j] )
             {
                   minimumDistanceMatrix[i][j] = minimumDistanceMatrix[i][k] + minimumDistanceMatrix[k][j];
                   shortestPathCalculatorMatrix [i][j] =  k;
             }
   

   Run Code Online (Sandbox Code Playgroud)

3. 然后 …

Skiena的算法书包含以下对Floyd Warshall算法的解释:

 floyd(adjacency_matrix *g)
 {
   int i,j; /* dimension counters */
   int k; /* intermediate vertex counter */
   int through_k; /* distance through vertex k */
   for (k=1; k<=g->nvertices; k++)
       for (i=1; i<=g->nvertices; i++)
           for (j=1; j<=g->nvertices; j++) {
                through_k = g->weight[i][k]+g->weight[k][j];
                if (through_k < g->weight[i][j])
                      g->weight[i][j] = through_k;
           }
  }

Floyd-Warshall全对最短路径在O(n ³)时间内运行,这渐渐没有比n调用Dijkstra算法更好.但是,循环非常紧凑,程序太短,以至于在实践中运行得更好.值得注意的是,稀有图算法之一在邻接矩阵上比邻接列表更好.

有人可以详细说明为什么大胆的部分是真的吗？

我正在尝试使用这个逻辑来理解邻接矩阵发生了什么,但是我认为它与关于abcd的间隔有关...

谁能解释一下这里发生了什么？

谢谢(标记为java作为它向我们展示的语言,所以如果有人发布任何代码示例,他们可以看到它是用那种语言)

http://compprog.wordpress.com/2007/11/15/all-sources-shortest-path-the-floyd-warshall-algorithm/

这是代码:

for (k = 0; k < n; ++k) {
    for (i = 0; i < n; ++i)
        for (j = 0; j < n; ++j)
            /* If i and j are different nodes and if
               the paths between i and k and between
               k and j exist, do */
            if ((dist[i][k] * dist[k][j] != 0) && (i != j))
                /* See if you can't get a shorter path
                   between i and j by …

我阅读了 floyd warshall 算法的伪代码 1 let dist be a |V| × |V| array of minimum distances initialized to ? (infinity) 2 for each vertex v 3 dist[v][v] ? 0 4 for each edge (u,v) 5 dist[u][v] ? w(u,v) // the weight of the edge (u,v) 6 for k from 1 to |V| 7 for i from 1 to |V| 8 for j from 1 to |V| 9 if dist[i][j] > dist[i][k] + dist[k][j] 10 dist[i][j] ? dist[i][k] + dist[k][j] 11 …