单源最短路径问题.docx

交运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);