您当前的位置： 首页 >  数据结构

【大话数据结构C语言】48 最短路径（弗洛伊德算法）

CodeAllen嵌入式编程 发布时间：2021-05-15 01:03:51 ，浏览量：4

欢迎关注我的公众号是【CodeAllen】，关注回复【1024】获取资源 程序员技术交流①群：736386324 ，程序员技术交流②群：371394777    

迪杰特斯拉算法对比弗洛伊德算法
O(n^2)   O(n^3)
 
可见前者是明显优于后者的
因为迪杰特斯拉算法求的是一个顶点到所有顶点的最短路径，但弗洛伊德算法是求所有顶点到所有顶点的最短路径。
弗洛伊德算法非常简洁优雅
 
弗洛伊德算法
弗洛伊德的核心思想是：对于网中的任意两个顶点（例如顶点 A 到顶点 B）来说，之间的最短路径不外乎有 2 种情况：
  1. 直接从顶点 A 到顶点 B 的弧的权值为顶点 A 到顶点 B 的最短路径；
  2. 从顶点 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 
关注
打赏
1688896170
查看更多评论

CodeAllen嵌入式编程

暂无认证

  • 4浏览

    0关注

    770博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

[ 申请 ]友情链接：

復刻手錶 快连vpn 快连 快连vpn 搜外友链 笔趣阁 爱思助手 ClashX教程 绘画宝宝 配音宝宝
0.4029s