关注
floyds(int a[][100],int n).
"a"和代表什么,a的两个维度分别代表什么?
"n"代表什么?
我有一个位置列表,其中包含这些位置之间的连接列表,并计算了相互连接的那些连接之间的距离。 现在我需要在任何给定的两个位置(floyd's)之间找到最短路径 - 但需要了解如何将floyds(int a[][100],int n)
应用于我的位置数组、城市词典和连接数组。
仅供参考 - 使用目标 C - iOS。
n
是图形中的节点数。
a
是图形的距离矩阵。 a[i][j]
是边从节点 i 到节点 j 的成本(或距离)。
(如果您需要有关该概念的更多帮助,另请阅读邻接矩阵的定义。
/* 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
维基很不错~~~
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}。在 min(W[i][j],W[i][k]+W[k][j])中,W[i][j] 是第 k 次迭代时 i 和 j 之间计算的最短路径,这里因为中间顶点来自集合 {1,2...k-1},所以此路径不包括顶点 k。在 W[i][k]+W[k][j] 中,我们在路径中包含顶点 k.两者之间的最小值是第 k 次迭代时的最短路径。基本上,我们检查是否应该在路径中包含顶点k。