【大话数据结构C语言】48 最短路径（弗洛伊德算法）
【摘要】
欢迎关注我的公众号是【CodeAllen】，关注回复【1024】获取资源 程序员技术交流①群：736386324 ，程序员技术交流②群：371394777
迪杰特斯拉算法对比弗洛伊德算法
O(n^2) O(n^3)
可见前...
欢迎关注我的公众号是【CodeAllen】，关注回复【1024】获取资源
程序员技术交流①群：736386324 ，程序员技术交流②群：371394777
迪杰特斯拉算法对比弗洛伊德算法
O(n^2) O(n^3)
可见前者是明显优于后者的
因为迪杰特斯拉算法求的是一个顶点到所有顶点的最短路径，但弗洛伊德算法是求所有顶点到所有顶点的最短路径。
弗洛伊德算法非常简洁优雅
弗洛伊德算法
弗洛伊德的核心思想是：对于网中的任意两个顶点（例如顶点 A 到顶点 B）来说，之间的最短路径不外乎有 2 种情况：
-
直接从顶点 A 到顶点 B 的弧的权值为顶点 A 到顶点 B 的最短路径；
-
从顶点 A 开始，经过若干个顶点，最终达到顶点 B，期间经过的弧的权值和为顶点 A 到顶点 B 的最短路径。
floyd.c
-
#define MAXVEX 9
-
#define INFINITY 65535
-
-
typedef int Pathmatirx[MAXVEX][MAXVEX];
-
typedef int ShortPathTable[MAXVEX][MAXVEX];
-
-
void ShortestPath_Floyd(MGraph G, Pathmatirx *P, ShortPathTable *D)
-
{
-
int v, w, k;
-
-
// 初始化D和P
-
for( v=0; v < G.numVertexes; v++ )
-
{
-
for( w=0; w < G.numVertexes; w++ )
-
{
-
(*D)[v][w] = G.matirx[v][w];
-
(*P)[v][w] = w;
-
}
-
}
-
-
// 优美的弗洛伊德算法
-
for( k=0; k < G.numVertexes; k++ )
-
{
-
for( v=0; v < G.numVertexes; v++ )
-
{
-
for( w=0; w < G.numVertexes; w++ )
-
{
-
if( (*D)[v][w] > (*D)[v][k] + (*D)[k][w] )
-
{
-
(*D)[v][w] = (*D)[v][k] + (*D)[k][w];
-
(*P)[v][w] = (*P)[v][k]; // 请思考：这里换成(*P)[k][w]可以吗？为什么？
-
}
-
}
-
}
-
}
-
}
文章来源: allen5g.blog.csdn.net，作者：CodeAllen的博客，版权归原作者所有，如需转载，请联系作者。
原文链接：allen5g.blog.csdn.net/article/details/116811983
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）