algorithm - 弗洛伊德算法解释

Question

关于

floyds(int a[][100],int n).

'a' 和代表什么以及 a 的两个维度中的每一个代表什么？

“n”代表什么？

我有一个位置列表，其中包含这些位置之间的连接列表，并计算了这些连接之间相互连接的距离。现在我需要找到任何给定两个位置（floyd's）之间的最短路径——但需要了解如何应用floyds(int a[][100],int n)到我的位置数组、城市词典和连接数组。

仅供参考 - 使用目标 C - iOS。

Answer 1

n是图中的节点数。

a是图的距离矩阵。a[i][j]是从节点 i 到节点 j 的边的成本（或距离）。

（如果您需要更多有关该概念的帮助，请阅读邻接矩阵的定义。）

Answer 2

/* Assume a function edgeCost(i,j) which returns the cost of the edge from i to j

2    (infinity if there is none).

3    Also assume that n is the number of vertices and edgeCost(i,i) = 0

4 */

5

6     int path[][];

7     /* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path

8        from i to j using intermediate vertices (1..k−1).  Each path[i][j] is initialized to

9        edgeCost(i,j).

10     */

12     procedure FloydWarshall ()

13        for k := 1 to n

14           for i := 1 to n

15              for j := 1 to n

16                 path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

http://en.wikipedia.org/wiki/Floyd-Warshall

维基很好~~~

Answer 3

floyd-warshall(W) // W is the adjacent matrix representation of graph..
 n=W.rows;
 for k=1 to n
    for i=1 to n
       for j=1 to n
            w[i][j]=min(W[i][j],W[i][k]+W[k][j]);
 return W;

这是一个 dp 算法。在第 k 次迭代中，W[i][j] 是 i 和 j 之间的最短路径，最短路径的顶点（不包括 i 和 j）来自集合 {1,2, 3...,k-1,k}.In min(W[i][j],W[i][k]+W[k][j]), W[i][j] 是计算的在第 k-1 次迭代时 i 和 j 之间的最短路径，因为中间顶点来自集合 {1,2...k-1}，所以这条路径不包括顶点 k。在 W[i][k]+W[k][j] 中，我们在路径中包含顶点 k。两者之间的最小值是第 k 次迭代的最短路径。基本上我们检查是否应该在路径中包含顶点 k。