首页 > 搜索 > java演示最短路径算法,最短路径之迪杰斯特拉算法的Java实现

java演示最短路径算法,最短路径之迪杰斯特拉算法的Java实现

互联网 2020-10-23 02:32:15
在线算命,八字测算命理

Dijkstra算法是最短路径算法中为人熟知的一种,是单起点全路径算法。该算法被称为是“贪心算法”的成功典范。本文接下来将尝试以最通俗的语言来介绍这个伟大的算法,并赋予java实现代码。

一、知识准备

1、表示图的数据结构

用于存储图的数据结构有多种,本算法中笔者使用的是邻接矩阵。

  图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息。

  设图G有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:

从上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴,右上角的元和左下角相对应的元全都是相等的。

    从这个矩阵中,很容易知道图中的信息。

    (1)要判断任意两顶点是否有边无边就很容易了;

    (2)要知道某个顶点的度,其实就是这个顶点vi在邻接矩阵中第i行或(第i列)的元素之和;

    (3)求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[i][j]为1就是邻接点;

    而有向图讲究入度和出度,顶点vi的入度为1,正好是第i列各数之和。顶点vi的出度为2,即第i行的各数之和。

有向图的定义也类似,故不做赘述。

2、单起点全路径

所谓单起点全路径,就是指在一个图中,从一个起点出发,到所有节点的最短路径。

 

3、图论的基本知识(读者需自行寻找相关资料)

 

4、互补松弛条件

设标量d1,d2,....,dN满足

dj di + aij(违反松弛条件),则令

dj = di + aij    , (如果j已经从V中移除过,说明其最小距离已经计算出,不参与此次计算)

可以看到在算法的运算工程中,节点的d值是单调不增的

具体算法图解如下

三、代码实现

//接受一个有向图的权重矩阵,和一个起点编号start(从0编号,顶点存在数组中)//返回一个int[] 数组,表示从start到它的最短路径长度  public static int[] Dijsktra(int[][]weight,int start){int length = weight.length;int[] shortPath = new int[length];//存放从start到各个点的最短距离shortPath[0] = 0;//start到他本身的距离最短为0String path[] = new String[length];//存放从start点到各点的最短路径的字符串表示for(int i=0;i
免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多