加权有向图与最短路径问题（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。

相关文章

Oracle查询优化之高效实现仅查询前10条记录的方法与实践

Oracle查询优化之高效实现仅查询前10条记录的方法与实践

《Oracle查询优化之高效实现仅查询前10条记录的方法与实践》：本文主要介绍Oracle查询优化之高效实现仅查询前10条记录的相关资料,包括使用ROWNUM、ROW_NUMBER()函数、FET... 目录1. 使用 ROWNUM 查询2. 使用 ROW_NUMBER() 函数3. 使用 FETCH FI
阅读更多...
Python脚本实现自动删除C盘临时文件夹

Python脚本实现自动删除C盘临时文件夹

《Python脚本实现自动删除C盘临时文件夹》在日常使用电脑的过程中,临时文件夹往往会积累大量的无用数据,占用宝贵的磁盘空间,下面我们就来看看Python如何通过脚本实现自动删除C盘临时文件夹吧... 目录一、准备工作二、python脚本编写三、脚本解析四、运行脚本五、案例演示六、注意事项七、总结在日常使用
阅读更多...
Java实现Excel与HTML互转

Java实现Excel与HTML互转

《Java实现Excel与HTML互转》Excel是一种电子表格格式,而HTM则是一种用于创建网页的标记语言,虽然两者在用途上存在差异,但有时我们需要将数据从一种格式转换为另一种格式,下面我们就来看看... Excel是一种电子表格格式，广泛用于数据处理和分析，而HTM则是一种用于创建网页的标记语言。虽然两
阅读更多...
java图像识别工具类(ImageRecognitionUtils)使用实例详解

java图像识别工具类(ImageRecognitionUtils)使用实例详解

《java图像识别工具类(ImageRecognitionUtils)使用实例详解》：本文主要介绍如何在Java中使用OpenCV进行图像识别,包括图像加载、预处理、分类、人脸检测和特征提取等步骤... 目录前言1. 图像识别的背景与作用2. 设计目标3. 项目依赖4. 设计与实现 ImageRecogni
阅读更多...
Java中Springboot集成Kafka实现消息发送和接收功能

Java中Springboot集成Kafka实现消息发送和接收功能

《Java中Springboot集成Kafka实现消息发送和接收功能》Kafka是一个高吞吐量的分布式发布-订阅消息系统,主要用于处理大规模数据流,它由生产者、消费者、主题、分区和代理等组件构成,Ka... 目录一、Kafka 简介二、Kafka 功能三、POM依赖四、配置文件五、生产者六、消费者一、Kaf
阅读更多...
Java访问修饰符public、private、protected及默认访问权限详解

Java访问修饰符public、private、protected及默认访问权限详解

《Java访问修饰符public、private、protected及默认访问权限详解》：本文主要介绍Java访问修饰符public、private、protected及默认访问权限的相关资料,每... 目录前言1. public 访问修饰符特点：示例：适用场景：2. private 访问修饰符特点：示例：
阅读更多...
详解Java如何向http/https接口发出请求

详解Java如何向http/https接口发出请求

《详解Java如何向http/https接口发出请求》这篇文章主要为大家详细介绍了Java如何实现向http/https接口发出请求,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 用Java发送web请求所用到的包都在java.net下，在具体使用时可以用如下代码，你可以把它封装成一
阅读更多...
关于@MapperScan和@ComponentScan的使用问题

关于@MapperScan和@ComponentScan的使用问题

《关于@MapperScan和@ComponentScan的使用问题》文章介绍了在使用`@MapperScan`和`@ComponentScan`时可能会遇到的包扫描冲突问题,并提供了解决方法,同时,... 目录@MapperScan和@ComponentScan的使用问题报错如下原因解决办法课外拓展总结@
阅读更多...
使用Python实现在Word中添加或删除超链接

使用Python实现在Word中添加或删除超链接

《使用Python实现在Word中添加或删除超链接》在Word文档中,超链接是一种将文本或图像连接到其他文档、网页或同一文档中不同部分的功能,本文将为大家介绍一下Python如何实现在Word中添加或... 在Word文档中，超链接是一种将文本或图像连接到其他文档、网页或同一文档中不同部分的功能。通过添加超
阅读更多...
MybatisGenerator文件生成不出对应文件的问题

MybatisGenerator文件生成不出对应文件的问题

《MybatisGenerator文件生成不出对应文件的问题》本文介绍了使用MybatisGenerator生成文件时遇到的问题及解决方法,主要步骤包括检查目标表是否存在、是否能连接到数据库、配置生成... 目录MyBATisGenerator 文件生成不出对应文件先在项目结构里引入“targetProje
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2