贪心算法-4.5单源最短路径之Dijkstra算法(松弛操作)

2024-01-10 04:32

本文主要是介绍贪心算法-4.5单源最短路径之Dijkstra算法(松弛操作),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

问题描述:对下图中的有向图,应用Dijkstra算法计算从源顶点1到其他顶点间最短路径的过程列在下页的表中。
1
问题分析
2

public class test4_5 {public static void Dijkstra(int v,float[][] a,float[] dist,int[] prev){int n = dist.length;if(v<0||v>n-1) return;boolean[] s = new boolean[n];//1.初始化   dist[i]、s[i]和prev[i]for(int i=0;i<n;i++){dist[i] = a[v][i];s[i] = false;if(dist[i]==Float.MAX_VALUE) prev[i] = -1;else prev[i] = v;}s[v] = true; dist[v] = 0;for(int i=0;i<n-1;i++){  //加进去n-1个点//2.找最小——找没加进去点连接的最小权值float temp = Float.MAX_VALUE;int u = v;for(int j=0;j<n;j++){if((!s[j])&&temp>dist[j]){  //没加进去的点&&temp>dist[j]temp = dist[j];u = j;}}s[u] = true;  //把点加进去//3.调整for(int j=0;j<n;j++){if((!s[j])&&dist[j]>a[u][j]+dist[u]){dist[j] = a[u][j]+dist[u];prev[j] = u;}}}}public static void main(String[] args) {int v = 0; //选定的源点为第"0"点int n = 5; //点的个数float t = Float.MAX_VALUE;float[][] a = {{t,10, t,30,100},  //邻接矩阵,表示边<i,j>的权值{t, t,50, t,  t},{t, t, t, t, 10},{t, t,20, t, 60},{t, t, t, t,  t}};float[] dist = new float[n];int[] prev = new int[n];Dijkstra(v,a,dist,prev);for(int i=0;i<n;i++){if(v!=i){System.out.print("从"+v+"点到"+i+"点所花的最短路长为:"+dist[i]+"; 路径是:"+i);int k = i;while(prev[k]!=-1){System.out.print("——"+prev[k]);k = prev[k];}}System.out.println();}}
}

运行结果:

从0点到1点所花的最短路长为:10.0; 路径是:1——0
从0点到2点所花的最短路长为:50.0; 路径是:2——3——0
从0点到3点所花的最短路长为:30.0; 路径是:3——0
从0点到4点所花的最短路长为:60.0; 路径是:4——2——3——0

时间复杂度:O(n^2)。

这篇关于贪心算法-4.5单源最短路径之Dijkstra算法(松弛操作)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/589549

相关文章

Java操作Word文档的全面指南

《Java操作Word文档的全面指南》在Java开发中,操作Word文档是常见的业务需求,广泛应用于合同生成、报表输出、通知发布、法律文书生成、病历模板填写等场景,本文将全面介绍Java操作Word文... 目录简介段落页头与页脚页码表格图片批注文本框目录图表简介Word编程最重要的类是org.apach

Python实现对阿里云OSS对象存储的操作详解

《Python实现对阿里云OSS对象存储的操作详解》这篇文章主要为大家详细介绍了Python实现对阿里云OSS对象存储的操作相关知识,包括连接,上传,下载,列举等功能,感兴趣的小伙伴可以了解下... 目录一、直接使用代码二、详细使用1. 环境准备2. 初始化配置3. bucket配置创建4. 文件上传到os

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

mysql表操作与查询功能详解

《mysql表操作与查询功能详解》本文系统讲解MySQL表操作与查询,涵盖创建、修改、复制表语法,基本查询结构及WHERE、GROUPBY等子句,本文结合实例代码给大家介绍的非常详细,感兴趣的朋友跟随... 目录01.表的操作1.1表操作概览1.2创建表1.3修改表1.4复制表02.基本查询操作2.1 SE

c++中的set容器介绍及操作大全

《c++中的set容器介绍及操作大全》:本文主要介绍c++中的set容器介绍及操作大全,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录​​一、核心特性​​️ ​​二、基本操作​​​​1. 初始化与赋值​​​​2. 增删查操作​​​​3. 遍历方

MySQL追踪数据库表更新操作来源的全面指南

《MySQL追踪数据库表更新操作来源的全面指南》本文将以一个具体问题为例,如何监测哪个IP来源对数据库表statistics_test进行了UPDATE操作,文内探讨了多种方法,并提供了详细的代码... 目录引言1. 为什么需要监控数据库更新操作2. 方法1:启用数据库审计日志(1)mysql/mariad

springboot如何通过http动态操作xxl-job任务

《springboot如何通过http动态操作xxl-job任务》:本文主要介绍springboot如何通过http动态操作xxl-job任务的问题,具有很好的参考价值,希望对大家有所帮助,如有错... 目录springboot通过http动态操作xxl-job任务一、maven依赖二、配置文件三、xxl-

Oracle 数据库数据操作如何精通 INSERT, UPDATE, DELETE

《Oracle数据库数据操作如何精通INSERT,UPDATE,DELETE》在Oracle数据库中,对表内数据进行增加、修改和删除操作是通过数据操作语言来完成的,下面给大家介绍Oracle数... 目录思维导图一、插入数据 (INSERT)1.1 插入单行数据,指定所有列的值语法:1.2 插入单行数据,指

SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志

《SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志》在SpringBoot项目中,使用logback-spring.xml配置屏蔽特定路径的日志有两种常用方式,文中的... 目录方案一:基础配置(直接关闭目标路径日志)方案二:结合 Spring Profile 按环境屏蔽关

SQL中JOIN操作的条件使用总结与实践

《SQL中JOIN操作的条件使用总结与实践》在SQL查询中,JOIN操作是多表关联的核心工具,本文将从原理,场景和最佳实践三个方面总结JOIN条件的使用规则,希望可以帮助开发者精准控制查询逻辑... 目录一、ON与WHERE的本质区别二、场景化条件使用规则三、最佳实践建议1.优先使用ON条件2.WHERE用