《最短路径的Dijkstra算法》由会员分享，可在线阅读，更多相关《最短路径的Dijkstra算法（11页珍藏版）》请在金锄头文库上搜索。
1、=实习报告二“最短路径的Dijkstr算法”演示程序（一）、程序的功能和特点1. 程序功能：建立带权网图的邻接矩阵，用Dijkstra算法算出任一点到其它点 的最短路径及其显示路线。2. 程序特点：采用java面向对象语言。将邻接矩阵用类封装，以实现对其方便 快捷的增修删的操作。用java实现最短路径算法。（二）、程序的算法设计算法一 “最短路径的Dijkstra”算法：1. 【逻辑结构与存储结构设计】逻辑结构：线性结构。存储结构：顺序存储结构。主要采用一维和二维数组实现最数据的存储和算法中间变量的存储。2. 【基本操作设计】首先，引进一个辅助向量D,它的每个分量Di表示当前所找到的从始点v到
2、每个终 点vi的最短路径的长度。它的初态为：若从v到vi有弧，则Di为弧上的权值；否则置Di 为显然，长度为：Dj=MinDil vie V的路径就是从v出发的长度最短的一条最短路 径。此路径为（v ,vj）。那么，下一条长度次短的最短是哪一条呢？假设该次短路径的终点 是vk，则可想而知，这条路径或者是（v, vk），或者是（v, vj, vk ）。它的长度或者是从v到 vk的弧上的权值，或者是Dj和从vj到vk的弧上的权值之和。依据前面介绍的算法思想，在一般情况下，下一条长度次短的最短路径的长度必是：Dj=MinDil vie V-S其中，Di或者弧（v, vi）上的权值，或者是Dk（ vk
3、eS和弧（vk, vi）上的权值之和。3. 【算法设计】迪杰斯特拉 （Dijkstra、算法思想：迪杰斯特拉（Dijkstra）提出的一个 按路径长度递增的次序产生最短路径的算法。该算法的基本思想是：设置两个顶 点的集合S和T=V S,集合S中存放已找到最短路径的顶点，集合T存放当前 还未找到最短路径的顶点。初始状态时，集合S中只包含源点v0，然后不断从 集合T中选取到顶点v0路径长度最短的顶点u加入到集合S中，集合S每加入 一个新的顶点u都要修改顶点v0到集合T中剩余顶点的最短路径长度值，集 合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点u的最短路径 长度值加上u到该顶点的路径长
4、度值中的较小值。此过程不断重复，直到集合T 的顶点全部加入到S中为止。算法文字说明：（1）假设用带权的邻接矩阵edges来表示带权有向图，edgesij表示 弧vi, vj上的权值。若vi, vj不存在，则置edgesij为在计 算机上可用允许的最大值代替）。S为已找到从v出发的最短路径的终点的集合, 它的初始状态为空集。那么，从v出发到图上其余各顶点（终点）vi可能达到 最短路径长度的初值为：Di= edgesLocate Vex（G,v）i vi eV（2）选择vj，使得Dj=MinDi| vie V-Svj就是当前求得的一条从v出发的最短路径的终点。令S = SU j（3）修改从v出发到
5、集合V-S上任一顶点vk可达的最短路径长度。如果 Dj+ edgesjkDk则修改Dk为Dk=Dj+ edgesjk重复操作（2）、（3）共n-1次。由此求得从v到图上其余各顶点的最短路径是 依路径长度递增的序列。算法流程图4. 【高级语言代码】/最短路径的ijks tra算法:public void Dijkstra(int vO) int s=new int MaxVeRtice ;int v,i,j,w;/* 初始化 s、dis t 和 pa th*/ for (v=0; vCurrentVertices; v+) sv=0; /* 0表示还未求出最短路径*/ /* 一开始假定取直达路径
6、最短*/ dis tv =EdgevOv;/*直达情况下的最后经由点就是出发点*/if (dist vMaxValue&v!二vO) pa th v=vO;else pathv=-l;/* 无直达路径 */*初始时源点vOeS集，表示vO到vO的最短路径已经找到*/ dist vO=O;svO = l;/下来假设经由一个点中转到达其余各点,会近些，验证之. /再假设经由两个点中转，会更近些，验证之,/直到穷举完所有可能的中转点. double min;for (i=l ;iCurrentVertices ;i+) /挑一个距离最近经由点，下标装入v min二MaxValue； for (w=O
7、;wCurrentVertices;w+)/*顶点w不属于S集且离vO更近*/ if (sw=O & dis t wmin) v=w; /*经由顶点w中转则距离更短*/ min=distw;sv = l; /*顶点v并入S,由vO到达v顶点的最短路径为min*/*假定由vO到v,再由v直达其余各点， 更新当前最后一个经由点及距离*/ for (j=O;jCurrentVertices;j+)if (sj=O & (min+Edgevj一个无向图的邻接矩阵表示r8963CX)9845CX)A=648873588888788一个网图的邻接矩阵表示2.【主要成员变量说明】主要成员变量有：static
8、 int MaxEdges = 50;最大边数。static int MaxVertices = 10;最大顶点数。static double MaxValue=9999.9;最大值无。private char VerticesList=new charMaxVertices;存放顶点的数组。private double Edge =new double MaxVerticesMaxVertices;邻接 矩阵(存放两个顶点权值)。private int CurrentEdges;现有边数。private int Curre nt Ver ti ces;现有顶点数public int path
9、=new int MaxVertices;存放最短路径上的最后一个经 由点。public double dist=new doubleMaxVertices;存放最短路径的权值。3. 【主要成员方法说明】public GraphPath ():构造函数建立空的邻接矩阵。 public int FindVertex (char ver tex):査找指定的顶点的序号。 public boolean IsGraphEmpty ():判断图是否为空。 public boolean IsGraphFull ():判断图是否为满。 public int NumberOfVertices ():取得顶点数
10、。public int NumberOfEdges ():取得边数。public char GetValue ( int i ):按序号取得顶点值。参数为顶点序号。 public double GetWeight ( int v1, int v2 ):取得一条边的权值，参 数为该边的顶点。public int GetFirstNeighbor ( int v ):取得第一个邻接点的序号。 public int InsertVer tex ( char ver tex ):插入一个顶点，参数为顶点. r.tt数据。public boolean InsertEdge( int v1, int v2
11、, double weight)： 插入一 条边，参数为连接该边的两个顶点及边上的权值。public boolean RemoveVertex ( int v )：删除一个顶点。public boolean RemoveEdge ( int v1, int v2 ):删除一条边，参数为 所删除边的两个顶点，既删除v1,v2顶点之间的连接边。public void display():打印邻接矩阵。public void Dijkstra(int vO)：最短路径的ijkstra算法，参数为起点。 public void Putpath(int vO)：输出 Dijkstra 算法的结果。4.
12、【高级语言代码】/ “邻接矩阵”类class GraphPath static int MaxEdges = 50;static int MaxVertices = 10;static double MaxValue=9999.9;/无穷大/存放顶点的数组private char VerticesList =new char MaxVertice ;/邻接矩阵(存放两个顶点权值)private double Edge =new double MaxVertice MaxVertice ; priva te int Curre nt Edges; /现有边数 priva te int Curre
13、 nt Ver ti ces; /现有顶点数/存放最短路径上的最后一个经由点 public int path=new int MaxVertice ； /存放最短路径的权值public double dist =new double MaxVertice ；/构造函数：建立空的邻接矩阵public GraphPath ( )for ( int i 二 0; i MaxVertice ； i+ ) for ( int j = 0; j MaxVertice ； j+ ) if (i=j)Edgeij = 0; /对角线else/非对角线上无穷大Edgeij二MaxValue；Curren tEdges = 0;/现有边数Curren
