你在找floyd算法的内容吗？ 把最受欢迎的东西献给你吧：
众所周知，Floyd算法用于求解最短路径。 floyd算法可以说是Warshall算法的扩展，它可以在三个for循环中解决问题，因此其时间复杂度为o(n^3)。
floyd算法的基本思想是，从任意节点a到任意节点b的最短路径只有两种可能性： 1直接从a到b，2从a经过几个节点x到b。 因此，假设dis[ab]为从节点a到节点b的最短路径的距离，针对每个节点x，调查dis[ax]dis[XB]dis[ab]是否成立，如果成立，则从a到x，再到b的路径是否为a
很简单吧。 代码可能看起来如下。
for(intI=0； I节点数； I )
{
for(intj=0； j节点数； j )
{
for(intk=0； k节点数； k )
{
if(dis[I][k]dis[k][j]dis[I][j] )
{
//找到更短的路径
Dis[i][j]=Dis[i][k] Dis[k][j]；
}
}
}
}
但是，在这里必须注意循环的嵌套顺序。 如果将检查所有节点x置于最内层，则结果不正确。 为什么呢？ 这是因为，从I到j的最短路径提前确定，之后存在更短的路径时，就不再更新。
请看一个例子。 请看下图。
图中的红色数字表示边的权重。 如果在最内层检查所有节点x，则对于A-B，只能找到路径距离为9的名为A-B的一条路径。 这显然不正确。 实际最短路径为A-D-C-B，路径距离为6。 错误的原因是把检查所有节点x放在最内层，提前决定了从a到b的最短路径，在决定了A-B的最短路径时Dis(AC还没有计算)。 因此，必须将循环顺序改写为：
for(intk=0； k节点数； k )
{
for(intI=0； I节点数； I )
{
for(intj=0； j节点数； j )
{
if(dis[I][k]dis[k][j]dis[I][j] )
{
//找到更短的路径
Dis[i][j]=Dis[i][k] Dis[k][j]；
}
}
}
}
以这种方式，对每个节点x处理所有I到j，然后继续检查下一个节点。
那么，下一个问题是如何找到最短路径？ 在这里，需要利用辅助数组Path。 这表示如果path(ab )的值为p，则从a节点到b节点的最短路径为a----p-b。 于是，如果要寻找A-B的最短路径，就按顺序寻找。 假设path(ab )的值为p，则接着搜索path(ab )，假设path(ab )的值为l，然后搜索path(ab )，假设path(ab )的值为a，则搜索结束。
那么，如何填充Path的值呢？ 很简单。 发现dis(ax ) dis(ax ) dis(ax )成立时，将最短路径更改为a--.-x--b。 此时，PATH ) XB )的值是已知的，因此为PATH ) ab )=PATH ) XB )。
好了，基本介绍结束了。 接下来是实现的时候了。 其中使用图和邻接矩阵：
#定义infinite 1000//最大值
#define MAX_VERTEX_COUNT 20//最大顶点数
//
结构图形
{
intarrarcs [ max _ vertex _ count ] [ max _ vertex _ count ]； //邻接矩阵
intnVertexCount；
//顶点数
intnArcCount；
//边数
(；
//
首先，写一个读取图数据的方法：
voidreadgraphdata (graph * _ pgraph )。
{
std3:cout '顶点的数量和边的数量3360 '；
STD :3360 CIN _ pgraph-nvertexcount；
STD :3360 CIN _ pgraph-narc count；
std:cout '相邻矩阵数据：' std:endl；
for(introw=0； row _pGraph-nVertexCount； row )
{
for (国际=0； col _pGraph-nVertexCount； col )
{
STD :3360 CIN _ pgraph-arr arcs [ row ] [ col ]；
}
}
}
其次，是核心floyd算法。
void Floyd (int _ arr dis [ ] [ max _ vertex _ count ]，int _ arr path [ ] [ max _ vertex _ count ]，int _nVertexCount
{
//先初始化_arrPath
for(intI=0； i _nVertexCount； I )
{
for(intj=0； j _nVertexCount； j )
{
_arrPath[i][j]=i；
}
}
//
for(intk=0； k _nVertexCount； k )
{
for(intI=0； i _nVertexCount； I )
{
for(intj=0； j _nVertexCount； j )
{
if (arr dis [ I ] [ k ] _ arr dis [ k ] [ j ] _ arr dis [ I ] [ j ] )
{
//找到更短的路径
_ arr dis [ I ] [ j ]=_ arr dis [ I ] [ k ] _ arr dis [ k ] [ j ]；
_arrPath[i][j]=_arrPath[k][j]；
}
}
}
}
}
确定，最后输出结果的数据代码：
本文来自电脑杂谈，转载请注明正文网站：
33558 www.PC-LHD lr.com/a/shenmilingyu/article-2435-1.html