- 1、本文档共5页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 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)