单源最短路径问题.docx

  1. 1、本文档共5页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
交运0701 小组成员: 胡连胜 1101070120 赵桂湖 1101070107 周文彬 1101070122 王 魁 1101070123 单源最短路径问题   问题描述   给定一个带权有向图 G=(V,E) ,其中每条边的权是一个非负实数。另外,还给定 V 中的一个顶点,称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。   单源最短路径问题   解决方案:Dijkstra提出按各顶点与源点v间的路径长度的递增次序,生成到各顶点的最短 路径的算法。既先求出长度最短的一条最短路径,再参照它求出长度次短的一条最短路径,依次类推,直到从源点v 到其它各顶点的最短路径全部求出为止。   问题的提出: 给定一个带权有向图G与源点v,求从v到G中其它顶点的最短路径。限定各边上的权值大于或等于0。   求单源最短路径的具体步骤   将图G中所有的顶点V分成两个顶点集合S和T。以v为源点已经确定了最短路径的终点并入S集合 中,S初始时只含顶点v,T则是尚未确定到源点v最短路径的顶点集合 C语言源程序代码如下: #include stdio.h #include conio.h int n=0; /*结点个数*/ int prev[100]; /*记录最短路径到i的前一个顶点*/ int s[101]; /**/ float a[100][100]; /*记录边的权值*/ float dist[100]; /*记录从源点到i的相应最短路径*/ #define MAX_VALUE 100000.0 void dijkstra(int v) { int i,j; if(v1 || vn) return; /*初始设置*/ for(i=1;i=n;i++) { dist[i]=a[v][i]; /*初始时从源点到i的最短路径设为从源点到i的权值*/ s[i]=1; /*s[i]=false*/ if(dist[i]==MAX_VALUE) prev[i]=0; /*从源点到i没有通路*/ else prev[i]=v; /*从源点到i有通路时,最短路径前一个结点设为源点*/ } dist[v]=0; /*源点到源点的最短路径为0*/ s[v]=0; /*s[v]=true*/ /*为下面循环中源点不参加比较做准备*/ /*中心部分*/ for(i=1;in;i++) { float temp=MAX_VALUE; int u=v; /*找出一个剩余结点中到源点最短的结点*/ for(j=1;j=n;j++) if((s[j]==1) (dist[j]temp)) /*如果该点不是源点并且源点到j点路径是最短*/ { u=j; /*u记录最短路径的点*/ temp=dist[j]; /*记录源点到j点的最短路径*/ } s[u]=0; /*s[u]=true*/ /*u点是下面进行比较的点*/ /*找出通过U点是否有更短的路径*/ for(j=1;j=n;j++) if((s[j]==1) (a[u][j]MAX_VALUE)) { float newdist=dist[u]+a[u][j]; if(newdistdist[j]) /*源点到u的路径+u到j的路径源点到j的路径*/ { dist[j]=newdist; /*更改源点到j的路径长度*/ prev[j]=u; /*更改源点到j的最短路径中,j的前一个结点*/ } } } } main() { int i,j,v; float temp; printf(Please input number of point:\n);

文档评论(0)

yurixiang1314 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档