迪杰斯特拉算法.docx

[日期] 迪杰斯特拉算法 姓名：陈应 学号专业：软件工程 语言：c++ 系统：win8 日期：2014.11.28 指导老师：赵宏宇  实验内容描述：建立字符文件，在文件内输入如下数据： m(为顶点数) i1 j1 k1(i1,j1构成一条边，k1为权重) i2 j2 k2 . . . 利用文件内的数据，使用邻接矩阵，建立又向连通网，采用迪杰斯特拉算法，得到有向连通网单源最短路经。输出指定顶点到其余顶点的最短路径及路径长度。 输入与输出设计: 用标志数组flag[N+1]表示两个集合，当flag[i]=0时表示顶点在集合V-S内，否则在集合S内 为集合S和集合V-S内的每个顶点设置一个距离值，集合S内顶点的距离值就为每个顶点的最短路径，而集合V-S内的顶点距离值为其顶点通过集合S内的顶点到达源点的最短路径 每次从集合V-S中选取距离值最小的顶点，加入到集合S中，此顶点的最短路径即为通过S中的顶点到达源点的最短路径，长度为??的此时的距离值。 每加入一个顶点到S中后，都要调整集合V-S中顶点的距离值 关键数据结构与算法: 邻接表存储网 迪杰斯特拉算法求最短路径 测试与结论 结论：测试正常，符合要求 源代码： #includeiostream #includefstream using namespace std; #define N 20 #define MAX 32767 /*MAX代表无穷大*/ typedef int AdiType; AdiType matrix[N+1][N+1]; //邻接矩阵 typedef struct { int prenode;//表示前点顶点; int pathlength; }shortestPath; shortestPath sp[N+1]; int flag[N+1]={0};//标志数组 /****求源点V到其余顶点的最短路径及长度***/ void dijisktra(int v,int n) { int i,j,m,k,min; flag[v]=1;//源点v进入集合S for(i=1;i=n;i++) { sp[i].pathlength=matrix[v][i];//置距离值 if((sp[i].pathlength!=0)sp[i].pathlength!=MAX) sp[i].prenode=v;//置前点序号 }//初始化路径长度及路径数组sp for(i=1;i=n;i++) { min=MAX; for(j=1;j=n;j++) { if((flag[j]==0)(sp[j].pathlengthmin)) {min=sp[j].pathlength;m=j;}//m点距离值最小 }//从集合V-S中找到距离值最小的点 flag[m]=1;//m点加入集合S for(k=1;k=n;k++) { if(flag[k]==0sp[m].pathlength+matrix[m][k]sp[k].pathlength) { sp[k].pathlength=sp[m].pathlength+matrix[m][k]; sp[k].prenode=m; } }//修改边集数组，调整距离值 } } /*****由前点数组求最短路径****/ void path(int v) { if(!sp[v].prenode)return; path(sp[v].prenode); coutsp[v].prenode-; } int main() { fstream file(D:\\tt.txt); int n,i,j,w,v; filen;//读入顶点数 for(i=1;i=n;i++) for(j=1;j=n;j++) if(i==j ) matrix[i][j]=0; else matrix[i][j]=MAX; while(fileijw) matrix[i][j]=w; cout请输入源点v:;cinv; dijisktra(v,n); cout源点v到各顶点最短路径及路径长度为:endl; for(i=1;i=n;i++) { if(i!=v) { path(i); couti:sp[i].pathlengthendl; } } coutendl; return 0; }