当前位置:码农谷 > 算法与程序 > 求最短路径的程序源代码(完整源码)

求最短路径的程序源代码(完整源码)

所属学科:Java语言 难度: 关注度:873

一、最短距离

求解城市之间的最短距离是一个非常实际的问题,其大意如下:

某地区有n个城市,如何选择路线使某个城市到某个指定城市的距离最短?

注意:这里需要求解的最短路径指的是两个城市之间的最短距离,而不是前面所讲的所有城市之间最短总距离。

1.1 最短路径算法

先来分析一下这个问题。某地区的n个城市构成一个交通图,仿照前面一节,这里仍然可以使用图结构来描述此问题,其对应关系如下:

•每个城市代表一个图中的一个顶点。

•两个顶点之间的边即两个城市之间的路径,边的权值代表了城市间的距离。

因此,求解两个城市之间的最短距离问题就归结为该图的最小路径问题。

对于一个带权图,一条路径的起始顶点往往称为源点,最后一个顶点为终点。对于图7-10所示的带权无向图,下面来分析每个顶点到顶点V1的最短路径。

•对于V2到V1,两者之间的最短路径即两者之间的边,路径权值为2;

•对于V3到V1,两者之间的最短路径即两者之间的边,路径权值为5;

•对于V4到V1,两者之间没有边,可以经过顶点2然后到达顶点1,此时路径权值为2+4=6;也可以经过顶点5然后到达顶点1,此时路径权值为2+3=5。因此,最短路径为经过顶点5 然后到达顶点1,路径权值为5;

•对于V5到V1,两者之间的最短路径即两者之间的边,路径权值为3;

在图中求解最短路径,可以采用如下算法:

(1) 将图中所有顶点的集合记为V,最小生成树中的顶点集合为U。初始时,V中包含所有顶点,而U中只有一个顶点V0。 

图片33.png 

图1带权无向图图的最短路径

(2) 然后,计算下一个顶点到顶点V0的最短路径,并将该顶点加入集合U中。

(3) 将上述步骤不断重复,直到全部顶点都加入集合U,这样便得到每个顶点到达顶点V0的最短路径。

按照此思路便可以编写相应的算法来求解最短路径。代码示例如下:

在上述代码中,定义了图的最大顶点数MaxNum和用于保存特殊符号Z的最大值MaxValue。数组path用于保存两点经过的顶点集合的数组,数组tmpvertex用于保存最短路径的起始点集合。

邻接矩阵图结构为GraphMatrk,其中包括保存顶点信息的数组Vertex,图的类型GType、顶点的数量VertexNum、边的数量EdgeNum、保存边的权的二维数组EdgeWeight及遍历标志数组isTrav。

方法DistMin()即最短路径算法,其输入参数GM为GraphMatrix结构的图数据,输入参数vend 为指定的终止点编号。程序中严格遵循了前述求解最短路径的算法,读者可以对照以加深理解。

1.2 最短路径求解

学习了前述图的最短路径算法后,便可以求解两个城市之间的最短距离问题。假设一个地区共有5个城市,如图2所示,各个城市之间道路的距离如下:

•城市1和城市2之间为2km;

•城市1和城市3之间为5km;

•城市1和城市5之间为3km:

•城市2和城市4之间为4km:

•城市3和城市5之间为5km:

•城市4和城市5之间为2km。

下面通过前述的图论求解最短路径的算法来求解各个城市到城市1之间的最短距离。完整的程序代码示例如下:

图片34.png 

图2 城市间的交通图

在上述代码中,图的处理部分参照了前面章节中关于图结构的算法。在主方法中,首先输入图的种类,0表示无向图,1表示有向图。然后输入顶点数和边数。接着清空图,并按照输入的数据生成邻接表结构的图。此时,由用户输入一个指定的结束点,然后调用DistMin()方法来求解各个顶点到达该指定结束点的最短路径。最后,将计算得到的最短路径结果输出显示。

整个程序的执行结果,这里按照题目的要求输入,这是一个无向图,包含4个顶点和6条边,将各个城市之间道路的距离作为权值输入。从图中的结果可知,各个城市到达城市 1的最短距离分别为:

•城市2到城市1的最短距离为2km.直接到达: 

•城市3到城市1的最短距离为5km,直接到达:

•城市4到城市1的最短距离为5km,中间经过城市5;

•城市5到城市1的最短距离为3km,直接到达。

程序源码

完整的程序源代码如下:

import java.util.Scanner;
 
class GraphMatrix2 
{  static final int  MaxNum=20; 
    char[] Vertex=new char[MaxNum];         //保存顶点信息(序号或字母)
    int GType;                  //图的类型(0:无向图,1:有向图)    
    int VertexNum;              //顶点的数量 
    int EdgeNum;                //边的数量 
    int[][] EdgeWeight=new int[MaxNum][MaxNum]; //保存边的权 
    int[] isTrav=new int[MaxNum];           //遍历标志 
}  
 
public class Demo_5 {
   static final int  MaxValue=65535;           //最大值(可设为一个最大整数)
   static int[] path=new int[GraphMatrix2.MaxNum];               //两点经过的顶点集合的数组
   static int[] tmpvertex=new int[GraphMatrix2.MaxNum];          //最短路径的起始点集合
   static Scanner input=new Scanner(System.in);
   static void CreateGraph(GraphMatrix2 GM)    //创建邻接矩阵图 
   {
       int i,j,k;

关注微信,获得更多免费资源
关于我们   |   免责声明   |   联系我们   |   网站地图   |   HR交流群   |   学生交流群   |   教师交流群

码农谷   版权所有 © 2015-2017   湘ICP备16018319号-1