单源最短路径.doc

2012-2013第2学期算法设计与分析实验报告单源最短路径专业班级智能科学与技术学号姓名1、实验环境Visual C+ 6.02、实验目的和要求给定一个带权有向图G=（V，E）,其中每条变得权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。3、解题思路、伪代码3.1解题思路设给定源点为Vs，S为已求得最短路径的终点集，开始时令S=Vs 。当求得第一条最短路径(Vs ，Vi)后，S为Vs，Vi 。根据以下结论可求下一条最短路径。设下一条最短路径终点为Vj ，则Vj只有：源点到终点有直接的弧；从Vs 出发到Vj 的这条最短路径所经过的所有中间顶点必定在S中。即只有这条最短路径的最后一条弧才是从S内某个顶点连接到S外的顶点Vj 。 若定义一个数组distn，其每个disti分量保存从Vs 出发中间只经过集合S中的顶点而到达Vi的所有路径中长度最小的路径长度值，则下一条最短路径的终点Vj必定是不在S中且值最小的顶点，即：disti=Min distk| VkV-S 利用公式就可以依次找出下一条最短路径。在程序中c表示带权邻接矩阵 ， dist表示顶点到源点的最短路径 ， p记录顶点到源点最短路径的前驱节点 ， u源点，函数Way是递归的构造出最短路径的次序。3.2 伪代码templatevoid Dijkstra(int n, int v, Type dist, int prev, Type *c)/单元最短路径问题的Dijkstra算法bool smaxint;for(int i=1; i=n; i+)disti = cvi;si = false;if(disti = maxint)previ = 0;elseprevi = v;distv = 0;sv = true;for(int i=1; in; i+)int temp = maxint;int u = v;for(int j=1; j=n; j+)if(!si)&(distjtemp)u = j;temp = distj;su = true;for(int j = 1; j=n; j+)if(!sj)&(cujmaxint)Type newdist = distu + cuj;if(newdistdistj)distj = newdist;prevj = u;4、实验步骤4.1实验代码：#include#include/Dijkstra算法实现函数void Dijkstra(int n,int v,int dist,int prev,int *cost) int i; int j; int maxint = 65535;/定义一个最大的数值，作为不相连的两个节点的代价权值 int *s ;/定义具有最短路径的节点子集s s = (int *)malloc(sizeof(int) * n); /初始化最小路径代价和前一跳节点值 for (i = 1; i = n; i+) disti = costvi; si = 0; if (disti = maxint) previ = 0; else previ = v; distv = 0; sv = 1;/源节点作为最初的s子集 for (i = 1; i n; i+) int temp = maxint; int u = v; /加入具有最小代价的邻居节点到s子集 for (j = 1; j = n; j+) if (!sj) & (distj temp) u = j; temp = distj; su = 1; /计算加入新的节点后，更新路径使得其产生代价最短 for (j = 1; j = n; j+) if (!sj) & (costuj maxint) int newdist = distu + costuj; if (newdist = 1; j-) printf(%d - ,wayj); printf(%dn,u);/主函数，主要做输入输出工作void main() int i,j,t; int n,v,u; int *cost;/代价矩阵 int *dist;/最短路径代价 int *prev;/前一跳节点空间 printf(please input the node number: ); scanf(%d,&n); printf(please input the cost status:n); cost=(int *)malloc(sizeof(int)*(n+1); for (i = 1; i = n; i+) costi=(int *)malloc(sizeof(int)*(n+1); /输入代价矩阵 for (j = 1; j = n; j+) for (t = 1; t = n; t+) scanf(%d,&costjt); dist = (int *)malloc(sizeof(int)*n); prev = (int *)malloc(sizeof(int)*n); printf(please input the source node: ); scanf(%d,&v); /调用dijkstra算法 Dijkstra(n, v, dist, prev, cost); printf(*n); printf(have confirm the best pathn); printf(*n); for(i = 1; i = n ; i+) if(i!=v) printf(the distance cost from node %d to node %d is %dn,v,i,disti); printf(the pre-node of node %d is node %d n,i,previ); ShowPath(n,v,i, dist, prev); 4.2输入：1.顶点数 2.接下来的n行描述这一个图形，采用邻接表方式，其中的第i行有n个数， 依次表示第i个顶点与第1、2、3、n个顶点的路径长。假如两个顶点间无边相连，用一个大数maxi