0

について

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

'a'とは何を表し、aの2つの次元のそれぞれは何を表しますか？

'n'は何を表しますか？

場所のリストと、それらの場所間の接続のリストがあり、相互に接続されている接続間の距離を計算しました。次に、任意の2つの場所（フロイド）間の最短経路を見つける必要がありますfloyds(int a[][100],int n)が、場所の配列、都市の辞書、および接続の配列に適用する方法を理解する必要があります。

参考までに-ObjectiveCを使用-iOS。

4

3 に答える 3

2

n is the number of nodes in the graph.

a is an distance matrix of the graph. a[i][j] is the cost (or distance) of the edge from node i to node j.

(Also read the definition of adjacency matrix if you need more help with the concept.)

于 2012-06-07T05:22:41.750 に答える
1 
/* 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

wikiはとても良いです~~~

于 2012-06-07T03:34:55.603 に答える
0 
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 を含めます。2 つの間の最小値は、k 回目の反復での最短パスです。基本的に、パスに頂点 k を含めるべきかどうかをチェックします。

于 2013-01-05T07:15:44.083 に答える