- #include <stdio.h>
- #define I 999 /* 代表两点间无直接相连 */
- /* Floyd Algorithm
- procedure ALL-PATHS(COST,A,n)
- // COST(n,n)是n结点图的成本邻接矩阵;
- // A(i,j)是结点vi到vj的最短路径的成本;
- // COST(i,i)=0,1≤i≤n
- integer i,j,k,n; real COST(n,n),A(n,n)
- for i←1 to n do
- for j←1 to n do
- A(i,j) ←COST(i,j) //用COST(i,j)对A0赋初值//
- repeat
- repeat
- for k←1 to n do //k控制Ak (i,j) //
- for i←1 to n do
- for j←1 to n do
- A (i,j) ← min{A (i,j) ,A (i,k) + A (k,j)}
- repeat
- repeat
- repeat
- end ALL-PATHS
- */
- /* 找a, b中的小值 */
- int f_min(int a, int b);
- /* example data
- cost[][] 为有向图的带权矩阵 */
- int cost[3][3] = {{ 0, 4, 41},
- { 6, 0, 2},
- { 3, I, 0}};
- /* A[][] 为两点间最短路径权值 */
- int A[3][3] = {{0}};
- /* 节点数目 */
- int n = 3;
- int main ()
- {
- int i, j, k;
- for(i = 1; i <= n; i++) {
- for (j = 1; j <= n; j++) {
- A[i-1][j-1] = cost[i-1][j-1];
- }
- }
- for(k = 1; k <= n; k++) {
- for(i = 1; i <= n; i++) {
- for(j = 1; j <= n; j++) {
- A[i-1][j-1] = f_min(A[i-1][j-1], A[i-1][k-1]+A[k-1][j-1]);
- }
- }
- }
- printf("the shortest path weight: \\n");
- for (i = 0; i < n; i++) {
- for (j = 0; j < n; j++)
- printf("%d ", A[i][j]);
- printf("\\n");
- }
- return 0;
- }
- int f_min (int a, int b)
- {
- return ((a > b) ? b : a);
- }
- //该片段来自于http://www.codesnippet.cn/detail/240720134794.html
来源: http://www.codesnippet.cn/detail/240720134794.html