加权有向图与最短路径问题（Dijstra算法，Java实现）

2023-11-02 00:38
文章标签 java 算法 实现 问题 路径 有向图 加权 dijstra

本文主要是介绍加权有向图与最短路径问题（Dijstra算法，Java实现），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

  • 1 加权有向图
    • 1.1 加权有向边的实现
    • 1.2 加权有向图的实现
  • 2 最短路径
    • 2.1 最短路径定义及性质
    • 2.2 松弛技术
    • 2.3 Dijstra算法思想
    • 2.4 Dijstra算法具体实现

1 加权有向图

加权无向图的边没有方向，一条边会同时出现在该边的两个顶点的邻接表中，为了能够处理含有方向性的图的问题，引入了加权有向图。

1.1 加权有向边的实现

API设计：

类名DirectedEdge
构造方法public DirectedEdge(int v, int w, double weight)：通过顶点v、w以及权重weight构造一个边对象
成员方法1. public double weight()：获取边的权重值
2.public int from()：获取有向边的起点
3.public int to()：获取有向边的终点
成员变量1.private final int v：起点
2.private final int w：终点
3.private final double weight：当前边的权重

代码：

public class DirectedEdge {private final int v;//起点private final int w;//终点private final double weight;//当前边的权重//通过顶点v、w以及权重weight构造一个边对象public DirectedEdge(int v, int w, double weight) {this.v = v;this.w = w;this.weight = weight;}//获取边的权重值public double weight(){return weight;}//获取有向边的起点public int from(){return v;}//获取有向边的终点public int to(){return w;}
}

1.2 加权有向图的实现

在加权无向图的基础上，把加权无向边替换成加权有向边即是加权有向图。

API设计：

类名EdgeWeightedDigraph
构造方法public EdgeWeightedDigraph(int V)：创建一个含有V个顶点的空加权有向图
成员方法1.public int V()：获取图中顶点的数量
2.public int E()：获取图中边的数量
3.public void addEdge(DirectedEdge e)：向加权有向图中添加一条边e
4.public Deque adj(int v)：获取由顶点v指出的所有边
5.public Deque edges()：获取加权有向图的所有边
成员变量1.private final int V：记录顶点数量
2.private int E：记录边数量
3.private Deque[] adj：邻接表

代码：

public class EdgeWeightedDigraph {//顶点总数private final int V;//边的总数private int E;//邻接表private Deque<DirectedEdge>[] adj;//创建一个含有V个顶点的空加权有向图public EdgeWeightedDigraph(int V) {//初始化顶点数量this.V = V;//初始化边的数量this.E = 0;//初始化邻接表this.adj = new Deque[V];for (int i = 0; i < adj.length; i++) {adj[i] = new LinkedList<>();}}//获取图中顶点的数量public int V() {return V;}//获取图中边的数量public int E() {return E;}//向加权有向图中添加一条边epublic void addEdge(DirectedEdge e) {//边e是有方向的，所以只需要让e出现在起点的邻接表中即可int v = e.from();adj[v].offer(e);E++;}//获取由顶点v指出的所有的边public Deque<DirectedEdge> adj(int v) {return adj[v];}//获取加权有向图的所有边public Deque<DirectedEdge> edges() {//遍历图中的每一个顶点，得到该顶点的邻接表，遍历得到每一条边，添加到队列中返回即可Deque<DirectedEdge> allEdges = new LinkedList<>();for (int v=0; v<V; v++){for (DirectedEdge edge : adj[v]) {allEdges.offer(edge);}}return allEdges;}
}

2 最短路径

加权有向图可以应用到实际生活中的很多场景，例如在地图中，找到顶点a与顶点b之间的路径，这条路径可以是距离最短，或者是时间最短，又或者是费用最小等，如果把距离/时间/费用看作成本，问题就转换为找到a和b之间成本最小的路径，即最短路径问题。

2.1 最短路径定义及性质

1 定义

在一副加权有向图中，从顶点s到顶点t的最短路径是指所有从顶点s到顶点t的路径中总权重最小的那条路径。

在这里插入图片描述

2 性质

  1. 路径具有方向性；
  2. 权重不一定是距离，也可以是时间、费用等内容，最短路径指的是总权重最低；
  3. 只考虑连通图。如果s和t不可达，它们之间就不存在最短路径，为了简化问题，这里只考虑连通图；
  4. 最短路径不一定唯一。从一个顶点到另一个顶点的最短路径可能有多条，这里只需找出一条即可；

3 最短路径树

  1. 给定一幅加权有向图和顶点s，以s为起点的一棵最短路径树是图的一幅子图，它包含起点s以及从s可达的所有顶点；
  2. 这棵有向树的根结点为s，树的每条路径都是有向图中的一条最短路径；

2.2 松弛技术

松弛这个词来源于生活：一条橡皮筋沿着两个顶点的某条路径紧紧拉开，如果这两个顶点之间的路径不止一条，还有存在更短的路径，那么把皮筋转移到更短的路径上，皮筋就可以放松了，松弛这种简单的原理刚好可以用来计算最短路径树。

边的松弛：

松弛边v->w意味着检查从s到w的最短路径是否是先从s到v，再从v到w：

  1. 如果是，将v-w这条边加入到最短路径树中，并更新edgeTo和distTo中的内容：edgeTo[w] = v->w，distTo[w] = distTo[v] + v->w的权重；
  2. 如果不是，忽略v->w；

顶点的松弛：

顶点的松弛是基于边的松弛完成的，只需要把某个顶点指出的所有边松弛，那么该顶点就松弛完毕。例如要松弛顶点v，只需遍历v的邻接表，把每一条边都松弛，那么顶点v就松弛了。

2.3 Dijstra算法思想

算法解析

  1. 找出权重最小的顶点；
  2. 对于该顶点的邻居，检查是否有前往它们的最短路径，如果有，就更新其权重（松弛）；
  3. 重复这个过程，直到对图中的每个顶点都这样做了；

算法实现

  1. 成员变量edgeTo存储起点到当前顶点的最短路径的最后一条边，成员变量distTo存储起点到当前顶点的最短路径的总权重；
  2. 开始给定图G和起点s，初始化起点s到s的最短路径的总权重distTo[s]=0，起点s到其他顶点的总权重为无穷大；
  3. 随着算法的执行，不断使用松弛技术处理图的边和顶点，更新edgeTo和distTo中的数据，最终就得到了最短路径树；

2.4 Dijstra算法具体实现

类名DijkstraSP
构造方法public DijkstraSP(EdgeWeightedDigraph G, int s)：根据一幅加权有向图G和顶点s，创建一个计算顶点为s的最短路径树对象
成员方法1.private void relax(EdgeWeightedDigraph G, int v)：松弛图G中的顶点v
2.public double distTo(int v)：获取从起点s到顶点v的最短路径的总权重
3.public boolean hasPathTo(int v)：判断从起点s到顶点v是否可达
4.public Deque pathTo(int v)：查询从起点s到顶点v的最短路径中所有的边
成员变量1.private DirectedEdge[] edgeTo：索引代表顶点，值表示从起点s到当前顶点的最短路径上的最后一条边
2.private double[] distTo：索引代表顶点，值为从起点s到当前顶点的最短路径的总权重
3.private indexMinPriorityQueue pq：存放树中顶点与非树中顶点之间的有效横切边

代码：

public class DijkstraSP {//索引代表顶点，值表示从顶点s到当前顶点的最短路径上的最后一条边private DirectedEdge[] edgeTo;//索引代表顶点，值表示从顶点s到当前顶点的最短路径的总权重private double[] distTo;//存放树中顶点与非树中顶点之间的有效横切边private IndexMinPriorityQueue<Double> pq;//根据一副加权有向图G和起点s，创建一个计算起点为s的最短路径树对象public DijkstraSP(EdgeWeightedDigraph G, int s){//初始化edgeTothis.edgeTo = new DirectedEdge[G.V()];//创建一个和图的顶点数一样大小的double数组，表示权重，并且初始化数组中的内容为无穷大，无穷大即表示不存在这样的边this.distTo = new double[G.V()];for (int i = 0; i < distTo.length; i++) {distTo[i] = Double.POSITIVE_INFINITY;}//创建一个和图的顶点数一样大小的索引最小优先队列，存储有效横切边this.pq = new IndexMinPriorityQueue<>(G.V());//默认让顶点s进入树中，但s顶点目前没有与树中其他的顶点相连接，因此初始化distTo[s]=0.0distTo[s] = 0.0;//使用顶点s和权重0.0初始化pqpq.insert(s,0.0);//遍历pqwhile(!pq.isEmpty()){//松弛图G中的顶点relax(G, pq.delMin());}}//松弛图G中的顶点vprivate void relax(EdgeWeightedDigraph G, int v){//松弛顶点v就是松弛顶点v邻接表中的每一条边，遍历邻接表for (DirectedEdge edge : G.adj(v)) {//获取到该边的终点wint w = edge.to();//通过松弛技术，判断从起点s到顶点w的最短路径是否需要先从顶点s到顶点v再由顶点v到顶点wif (distTo(v) + edge.weight() < distTo(w)){distTo[w] = distTo[v] + edge.weight();edgeTo[w] = edge;//如果顶点w已经存在于索引最小优先队列pq中，则重置顶点w的权重if (pq.contains(w)){pq.changeItem(w, distTo(w));}else{//如果顶点w没有出现在优先队列pq中，则把顶点w及其权重加入到pq中pq.insert(w, distTo(w));}}}}//获取从顶点s到顶点v的最短路径的总权重public double distTo(int v){return distTo[v];}//判断从顶点s到顶点v是否可达public boolean hasPathTo(int v){return distTo[v]<Double.POSITIVE_INFINITY;}//查询从起点s到顶点v的最短路径中所有的边public Deque<DirectedEdge> pathTo(int v){//如果顶点s到v不可达，则返回nullif (!hasPathTo(v)){return null;}//创建队列保存最短路径的边Deque<DirectedEdge> allEdges = new LinkedList<>();//从顶点v开始，逆向寻找，一直找到顶点s为止，而起点s为最短路径树的根结点，所以edgeTo[s]=nullwhile (true){DirectedEdge e = edgeTo[v];if (e==null){break;}allEdges.offer(e);v = e.from();}return allEdges;}
}

public class Test {public static void main(String[] args) {EdgeWeightedDigraph g = new EdgeWeightedDigraph(8);DirectedEdge e1 = new DirectedEdge(4,5,0.35); DirectedEdge e2 = new DirectedEdge(4,7,0.37);DirectedEdge e3 = new DirectedEdge(5,7,0.28); DirectedEdge e4 = new DirectedEdge(5,4,0.35);DirectedEdge e5 = new DirectedEdge(7,5,0.28); DirectedEdge e6 = new DirectedEdge(5,1,0.32);DirectedEdge e7 = new DirectedEdge(0,4,0.38); DirectedEdge e8 = new DirectedEdge(0,2,0.26);DirectedEdge e9 = new DirectedEdge(7,3,0.39); DirectedEdge e10 = new DirectedEdge(1,3,0.29);DirectedEdge e11 = new DirectedEdge(2,7,0.34); DirectedEdge e12 = new DirectedEdge(6,2,0.40);DirectedEdge e13 = new DirectedEdge(3,6,0.52); DirectedEdge e14 = new DirectedEdge(6,0,0.58);DirectedEdge e15 = new DirectedEdge(6,4,0.93);g.addEdge(e1);g.addEdge(e2);g.addEdge(e3);g.addEdge(e4);g.addEdge(e5);g.addEdge(e6);g.addEdge(e7);g.addEdge(e8);g.addEdge(e9);g.addEdge(e10);g.addEdge(e11);g.addEdge(e12);g.addEdge(e13);g.addEdge(e14);g.addEdge(e15);//根据图g和顶点0，构建PrimMST对象DijkstraSP dsp = new DijkstraSP(g, 0);//获取起点0到顶点6的最短路径Deque<DirectedEdge> edges = dsp.pathTo(6);//打印输出for (DirectedEdge edge : edges) {System.out.println(edge.from() + "->" + edge.to() + ":" + edge.weight());}}
}

3->6:0.52
7->3:0.39
2->7:0.34
0->2:0.26

注：

类IndexMinPriority可在索引最小优先队列的实现_sc179的博客-CSDN博客中找到

这篇关于加权有向图与最短路径问题（Dijstra算法，Java实现）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/326889。

相关文章

JVM 的类初始化机制

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时，有没有考虑过 JVM 是如何把静态的字节码（byte code）转化为运行时对象的呢，这个问题看似简单，但清楚的同学相信也不会太多，这篇文章首先介绍 JVM 类初始化的机制，然后给出几个易出错的实例来分析，帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段，分别是：loading 、Linking、initialization
阅读更多...
Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
浅析Spring Security认证过程

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程，特意画了如下的类图，包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口，接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti
阅读更多...
Spring Security--Architecture Overview

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类，它们之间的依赖，构建起了整个框架。想要理解整个架构，最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文（security context）的信息。当前操作的用户是谁，该用户是否已经被认证，他拥有哪些角色权限…这些都被保
阅读更多...
Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java架构师知识体认识

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
Java进阶13讲__第12讲_1/2

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory
阅读更多...
好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2