单源最短路径问题.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 #include int n=0; /*结点个数*/int prev100; /*记录最短路径到i的前一个顶点*/int s101; /*/float a100100; /*记录边的权值*/float dist100; /*记录从源点到i的相应最短路径*/#define MAX_VALUE 100000.0void dijkstra(int v) int i,j; if(vn) return; /*初始设置*/ for(i=1;i=n;i+) disti=avi; /*初始时从源点到i的最短路径设为从源点到i的权值*/ si=1; /*si=false*/ if(disti=MAX_VALUE) previ=0; /*从源点到i没有通路*/ else previ=v; /*从源点到i有通路时，最短路径前一个结点设为源点*/ distv=0; /*源点到源点的最短路径为0*/ sv=0; /*sv=true*/ /*为下面循环中源点不参加比较做准备*/ /*中心部分*/ for(i=1;in;i+) float temp=MAX_VALUE; int u=v; /*找出一个剩余结点中到源点最短的结点*/ for(j=1;j=n;j+) if(sj=1) & (distjtemp) /*如果该点不是源点并且源点到j点路径是最短*/ u=j; /*u记录最短路径的点*/ temp=distj; /*记录源点到j点的最短路径*/ su=0; /*su=true*/ /*u点是下面进行比较的点*/ /*找出通过U点是否有更短的路径*/ for(j=1;j=n;j+) if(sj=1) & (aujMAX_VALUE) float newdist=distu+auj; if(newdistdistj) /*源点到u的路径+u到j的路径源点到j的路径*/ distj=newdist; /*更改源点到j的路径长度*/ prevj=u; /*更改源点到j的最短路径中，j的前一个结点*/ main() int i,j,v; float temp; printf(Please input number of point:n); scanf(%d,&n); /*输入结点的个数*/ printf(Now input length i to j:n); for(i=1;i=n;i+) for(j=1;jj的权值*/ if(aij=0.0) aij=MAX_VALUE; /*输入为0表示没有通路，改为最大值*/ if(i=j) aij=0.0; /*i-i的权值为0*/ /* for(i=1;i=n;i+) for(j=1;j=n;j+) printf(%ft,aij); printf(n); */ printf(Now input v point(0point=%d):n,n); scanf(%d,&v); /*输入起始结点*/ dijkstra(v); printf(-n); /*设置输出*/ for(i=1;i=n;i+) if(i!=v & distiMAX_VALUE) /*源点到源点；源点到某点最长路径为无穷大的都不需要输出*/ printf(nfrom %d to %d,the shortest way is %g fa