C++实现Floyd算法
1，原理2，举例3，代码实现
1，原理
Floyd算法用来求解所有顶点间的最短距离，可以应用于有向图和无向图。基本思想是，先用矩阵存储各个点间的直达路径，然后将各个顶点依次加入，每加入一个顶点，就以该点为中间点，计算各个点间的路径在通过该中间点的情况下是否比原来的短，若短，则更新路径长度。将所有顶点都加入后，所得矩阵的每个数据就是对应两点间的最短路径。
2，举例
如图，以无向图为例 1，用初始矩阵dist存储各个点的直达路径距离，dist[i][j]表示从vi到vj的距离，各个点到自身距离为0，若两点无法直达，则距离为Max。（这里因为是无向图，所以 dist[i][j] = dist[j][i] ） 2，将v0点加入，由于dist[2][0] + dist[0][3] = 5 < dist[2][3] = 6, 所以 dist[2][3] = dist[3][2] = 5; 同理，dist[2][0] + dist[0][1] = 3 < dist[2][1] = Max, 所以 dist[2][1] = dist[1][2] = 3;
3,继续加入顶点更新矩阵，待全部加入后，所得矩阵中 dist[i][j] 的值即为从vi到vj得最短距离。
3，代码实现
#include<iostream>
using namespace std
;
#define Max 9999
int n
, m
;
int dist
[Max
][Max
];
void Floyd()
{
for (int i
= 0; i
< n
; ++i
)
{
for (int j
= 0; j
< n
; ++j
)
{
for (int p
= 0; p
< n
; ++p
)
{
if (dist
[j
][p
] > dist
[j
][i
] + dist
[i
][p
])
{
dist
[j
][p
] = dist
[j
][i
] + dist
[i
][p
];
}
}
}
}
}
int main()
{
cout
<< "输入节点数: ";
cin
>> n
;
cout
<< "输入边数：";
cin
>> m
;
for (int i
= 0; i
< n
; ++i
)
{
for (int j
= 0; j
< n
; ++j
)
{
if (j
== i
)
{
dist
[i
][j
] = 0;
}
else
{
dist
[i
][j
] = Max
;
}
}
}
int u
, v
, w
;
cout
<< "输入各条边的信息：" << endl
;
for (int i
= 0; i
< m
; ++i
)
{
cin
>> u
>> v
>> w
;
dist
[u
][v
] = dist
[v
][u
] = w
;
}
Floyd();
for (int i
= 0; i
< n
; ++i
)
{
for (int j
= 0; j
< n
; ++j
)
{
cout
<< dist
[i
][j
] << " \t";
}
cout
<< endl
;
}
return 0;
}
输入输出信息
