Floyd算法——最短路径算法_C语言实现_阿涵_新浪博客

?[订阅]
RSS
博客首页 登录 注册 记录下你的微生活
发博文
博文 搜索
阿涵
https://www.wendangku.net/doc/326424739.html,/jiangafu [订阅 ] [ 手机订阅 ]
首页 博文目录 图片 关于我
个人资料
阿涵
播客 微博
加好友 发纸条
写留言 加关注
博客等级：
博客积分： 627
博客访问： 9,628
关注人气： 7
相关博文
博客生活的最佳伴侣
新浪官博
更多>>
推荐博文
水木清华之图书馆篇：读书之乐
微软亚洲研究院
IDC市场进入自由定价时代
康斯坦丁
2011仍是App?Store开发者的好年
康斯坦丁
自由定价模式对网站建设市场的
于斌
开放透明是华为2010年报最大亮
刘启诚
与客户共同创新（一）
惠普中国研究院
有一种生活叫“Smarter?life”
杨宇良
南周妖魔化百度：是报道，还是
陈佼
网络低俗广告的鉴定标准
阿祥
告诉大家一个更加透明的华为
海天一峰
查看更多 >>
谁看过这篇博文
加载中…
正文 字体大小： 大 中 小
Floyd算法——最短路径算法?C语言实现 (2010-12-26 18:19:33) 转载
标签： floyd算法最短路径算法 c语言实现 it 分类： c.java.python
#define MAX_VERTEX_NUM 100 //最大顶点数
#define MAX_INT 10000 //无穷大
typedef int AdjType;
typedef struct{
int pi[MAX_VERTEX_NUM];//存放v到vi的一条最短路径
int end;
}PathType;
typedef char VType; //设顶点为字符类型
typedef struct{
VType V[MAX_VERTEX_NUM]; //顶点存储空间
AdjType A[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
}MGraph;//邻接矩阵表示的图
//Floyd算法
//求网G（用邻接矩阵表示）中任意两点间最短路径
//D[][]是最短路径长度矩阵，path[][]最短路径标志矩阵
void Floyd(MGraph * G,int path[][MAX_VERTEX_NUM],int D[][MAX_VERTEX_NUM],int n){
int i,j,k;
for(i=0;ifor(j=0;jif(G->A[i][j]path[i][j]=j;
}else{
path[i][j]=-1;
}
D[i][j]=G->A[i][j];
}
}
for(k=0;kfor(i=0;ifor(j=0;jif(D[i][j]>D[i][k]+D[k][j]){
D[i][j]=D[i][k]+D[k][j];//取小者
path[i][j]=path[i][k];//改Vi的后继
}
}
}
}
}
int main(){
int i,j,k,v=0,n=6;//v为起点，n为顶点个数
MGraph G;
int path[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//v到各顶点的最短路径向量
int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//v到各顶点最短路径长度向量
//初始化
AdjType a[MAX_VERTEX_NUM][MAX_VERTEX_NUM]={
{0,12,18,MAX_INT,17,MAX_INT},
{12,0,10,3,MAX_INT,5},
{18,10,0,MAX_INT,21,11},
{MAX_INT,3,MAX_INT,0,MAX_INT,8},
{17,MAX_INT,21,MAX_INT,0,16},
{MAX_INT,5,11,8,16,0}
};
for(i=0;ifor(j=0;jG.A[i][j]=a[i][j];
}
}
Floyd(&G,path,D,6);
for(i=0;ifor(j=0;jprintf("V%d到V%d的最短长度:",i,j);
printf("%d\t",D[i][j]);//输出Vi到Vj的最短路径长度
k=path[i][j];//取路径上

Vi的后续Vk
if(k==-1){
printf("There is no path between V%d and V%d\n",i,j);//路径不存在
}else{
printf("最短路径为:");
printf("(V%d",i);//输出Vi的序号i
while(k!=j){//k不等于路径终点j时
printf(",V%d",k);//输出k
k=path[k][j];//求路径上下一顶点序号
}
printf(",V%d)\n",j);//输出路径终点序号
}
printf("\n");
}
}
system("pause");
return 0;
}
分享
0
顶
阅读 (121) ┊ 评论 (0) ┊ 收藏 (0) ┊ 转载 ┊ 顶 ▼ ┊ 打印 ┊ 举报
已投稿到： 排行榜 圈子
前一篇： Dijkstra算法——最短路径问题（C语言实现）
后一篇： 数据结构?队列——循环队列、链式队列（C语言实现）
评论 重要提示：警惕虚假中奖信息 专门为您成立的博客俱乐部 关注每日最热门博客 [ 发评论 ]
当第一个评论者吧！ 抢沙发>>
发评论 更快捷的博文发布方法小浪带你畅游京城 关注每日最热门博客
更多>>
登录名： 密码： 找回密码 注册 记住登录状态
分享到微博 评论并转载此博文
验证码： 请点击后输入验证码 收听验证码 匿名评论
发评论
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。
后一篇?> 数据结构?队列——循环队列、链式队列（C语言实现）
新浪BLOG意见反馈留言板不良信息反馈 电话：4006900000 提示音后按1键（按当地市话标准计费）　欢迎批评指正
新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑
Copyright ? 1996 - 2011 SINA Corporation, All Rights Reserved
新浪公司 版权所有