java实现Dijkstra算法
作者:南 墙 发布时间:2021-09-02 23:14:15
本文实例为大家分享了java实现Dijkstra算法的具体代码,供大家参考,具体内容如下
1 问题描述
何为Dijkstra算法?
Dijkstra算 * 能:给出加权连通图中一个顶点,称之为起点,找出起点到其它所有顶点之间的最短距离。
Dijkstra算法思想:采用贪心法思想,进行n-1次查找(PS:n为加权连通图的顶点总个数,除去起点,则剩下n-1个顶点),第一次进行查找,找出距离起点最近的一个顶点,标记为已遍历;下一次进行查找时,从未被遍历中的顶点寻找距离起点最近的一个顶点, 标记为已遍历;直到n-1次查找完毕,结束查找,返回最终结果。
2 解决方案
2.1 使用Dijkstra算法得到最短距离示例
此处借用文末参考资料1博客中一个插图(PS:个人感觉此图描述简单易懂):
2.2 具体编码
Dijkstra复杂度是O(N^2),如果用binary heap优化可以达到O((E+N)logN),用fibonacci heap可以优化到O(NlogN+E) 。
注意,Dijkstra算法只能应用于不含负权值的图。因为在大多数应用中这个条件都满足,所以这种局限性并没有影响Dijkstra算法的广泛应用。
其次,大家要注意把Dijkstra算法与寻找最小生成树的Prim算法区分开来。两者都是运行贪心法思想,但是Dijkstra算法是比较路径的长度,所以必须把起点到相应顶点之间的边的权重相加,而Prim算法则是直接比较相应边给定的权重。
下面的代码时间复杂度为O(N^2),代码中所用图为2.1使用Dijkstra算法得到最短距离示例中所给的图。
package com.liuzhen.chapter9;
public class Dijkstra {
/*
* 参数adjMatrix:为图的权重矩阵,权值为-1的两个顶点表示不能直接相连
* 函数功能:返回顶点0到其它所有顶点的最短距离,其中顶点0到顶点0的最短距离为0
*/
public int[] getShortestPaths(int[][] adjMatrix) {
int[] result = new int[adjMatrix.length]; //用于存放顶点0到其它顶点的最短距离
boolean[] used = new boolean[adjMatrix.length]; //用于判断顶点是否被遍历
used[0] = true; //表示顶点0已被遍历
for(int i = 1;i < adjMatrix.length;i++) {
result[i] = adjMatrix[0][i];
used[i] = false;
}
for(int i = 1;i < adjMatrix.length;i++) {
int min = Integer.MAX_VALUE; //用于暂时存放顶点0到i的最短距离,初始化为Integer型最大值
int k = 0;
for(int j = 1;j < adjMatrix.length;j++) { //找到顶点0到其它顶点中距离最小的一个顶点
if(!used[j] && result[j] != -1 && min > result[j]) {
min = result[j];
k = j;
}
}
used[k] = true; //将距离最小的顶点,记为已遍历
for(int j = 1;j < adjMatrix.length;j++) { //然后,将顶点0到其它顶点的距离与加入中间顶点k之后的距离进行比较,更新最短距离
if(!used[j]) { //当顶点j未被遍历时
//首先,顶点k到顶点j要能通行;这时,当顶点0到顶点j的距离大于顶点0到k再到j的距离或者顶点0无法直接到达顶点j时,更新顶点0到顶点j的最短距离
if(adjMatrix[k][j] != -1 && (result[j] > min + adjMatrix[k][j] || result[j] == -1))
result[j] = min + adjMatrix[k][j];
}
}
}
return result;
}
public static void main(String[] args) {
Dijkstra test = new Dijkstra();
int[][] adjMatrix = {{0,6,3,-1,-1,-1},
{6,0,2,5,-1,-1},
{3,2,0,3,4,-1},
{-1,5,3,0,2,3},
{-1,-1,4,2,0,5},
{-1,-1,-1,3,5,0}};
int[] result = test.getShortestPaths(adjMatrix);
System.out.println("顶点0到图中所有顶点之间的最短距离为:");
for(int i = 0;i < result.length;i++)
System.out.print(result[i]+" ");
}
}
运行结果:
顶点0到图中所有顶点之间的最短距离为:
0 5 3 6 7 9
来源:https://blog.csdn.net/a1439775520/article/details/96903328
猜你喜欢
- 以前只知道控件的onTouchEvent()事件,它的动作有MotionEvent.ACTION_DOWN、MotionEvent.ACTI
- net 原则上禁止跨线程访问控件,因为这样可能造成错误的发生,推荐的解决方法是采用代理,用代理方法来间接操作不是同一线程创建的控件。第二种方
- 前言在开始本文之前要说明以下,首先我是一个初学springmvc,抱着去加深印象的目的去整理相关springmvc4的相关注解,同时也希望给
- 今天再学习一些C#的基础知识,如对 Int Array进行排序:你可以在控制台应用程序中,创建一个类别,它属性和2个构造函数:Source
- 本文实例为大家分享了java微信公众号支付示例代码,供大家参考,具体内容如下开始之前,先准备好:appid、商家号、商户密匙。工具类:MD5
- 一、Kt调用-Java参数非null的处理@NotNullclass TestJava { public void
- Java 开发语言中实现HTTP请求的方法主要有两种:一种是JAVA的标准类HttpUrlConnection,比较原生的实现方法;另一种是
- springboot去除控制台打印的debug日志1.创建logback-spring.xml文件文件内容如下<?xml versio
- 这篇文章主要介绍了Java JVM程序指令码实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友
- 这篇文章主要介绍了spring boot 2整合swagger-ui过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的
- Intellij IDEA 公司 JetBrains 推出了一种新字体:JetBrains Mono,它是专为开发人员设计的。为什么说它是专
- 做为面试常考的问题之一,每次都答的模模糊糊,有必要了解一下,首先来看一下hashmap的put方法的源码public V put(K key
- Android DragVideo实现播放视频时任意拖拽DragVideoA Method to Drag the Video When P
- 前置导入什么是多环境?其实就是说你的电脑上写的程序最终要放到别人的服务器上去运行。每个计算机环境不一样,这就是多环境。常见的多环境开发主要兼
- 写在前面本文由markdown格式写成,为本人第一次这么写,排版可能会有点乱,还望各位海涵。 主要写的是使用Ribbon进行Res
- 1、什么是序列化与反序列化?序列化:指把堆内存中的 Java 对象数据,通过某种方式把对象存储到磁盘文件中或者传递给其他网络节点(在网络上传
- 前言在原生的 Android 或 iOS 中,都提供了基本的键值对存储方式,Android 是 SharedPreferences,iOS
- 关于ListBoxListBox是WinForm中的列表控件,它提供了一个项目列表(一组数据项),用户可以选择一个或者多个条目,当列表项目过
- 在阅读这篇文章之前,大家可以先看下《Java多线程atomic包介绍及使用方法》,了解atomic包的相关内容。一、何谓Atomic?Ato
- 1. 你知道线程安全问题吗?线程安全问题:一般指在多线程模式下,多个线程对同一个共享数据进行操作时,第一个线程还没来得及更新共享数据,从而导