0401概述-最短路径-加权有向图-数据结构和算法(Java)

news/2024/3/28 22:41:36/文章来源:https://blog.csdn.net/gaogzhen/article/details/130375276

文章目录

    • 1 最短路径
    • 2 最短路径的性质
    • 3 加权有向图的数据结构
      • 3.1 加权有向边
      • 3.2 加权有向图
    • 4 最短路径
      • 4.1 最短路径API
      • 4.2 最短路径的数据结构
      • 4.3 边的松弛
      • 4.4 顶点的松弛
    • 结语

1 最短路径

如图1-1所示,一幅加权有向图和其中的一条最短路径:

在这里插入图片描述

定义:在一幅加权有向图中,从顶点t到顶点s的最短路径是所有从s到t的路径中权重最小者。

**单点最短路径。**给定一幅加权有向图和一个起点s,回答“从s到给定目的顶点v是否存在一条有向路径?如果有,找出最短(总权重最小)的那条路径。“等类似问题。

2 最短路径的性质

最短路径问题的基本定义很简单,但是有些问题需要我们解决:

  • **路径上有向的。**最短路径需要考虑到各条边的方向。
  • **权重不一定等价于距离。**权重可以表示时间、花费等,也不一定 和距离的远近成正比。
  • **并不是所有顶点都是可达的。**如果t并不是从s可达的,那么就不存在任何路径,也就不存在从s到t到最短路径。为了简化问题,我们的样图都是强连通的。
  • **父权重会使问题更复杂。**我们暂时假设边的权重都是正的(或零),父权重在后面讨论。
  • 最短路径一般都是简单的。我们的算法会忽略构成环的零权重边,因此找到的最短路径都不会含有环。
  • **最短路径不一定是唯一的。**从一个顶点到达另一个顶点的权重最小的路径可能有多条,我们只要找到其中一条即可。
  • **可能存在平行边或自环。**平行边中的权重最小者才会被选中,最短路径也不可能包含自环(除非自环的权重为零,但我们会忽略它)。为零避免歧义我们隐式地假设平行边不存在,用v->w表示从v到w到边。

我们的重点是单点最短路径问题,其中给出起点s,计算的结果是一棵最短路径树(SPT),它包含了顶点s到所有可达到顶点的最短路径。如图2-1所示:

在这里插入图片描述

给定一幅加权有向图和一个顶点s,以s为起点的一颗最短路径树树图的一幅子图,它包含s和从s可达的所有顶点。这颗有向树的根结点为s,树中的每条路径都是有向图中的一条最短路径。

3 加权有向图的数据结构

3.1 加权有向边

有向边的数据结构比无向边简单,因为有向边只有一个方向,这里定义了from()和to()方法,API如下表3.1-1所示:

public classDirectedEdge
publicDirectedEdge(int v, int w, double weight)
public doubleweight()边的权重
public intfrom()指出这条边的顶点
public intto()这条边指向的顶点
public StringtoString()对象的字符串表示

有向边DirectedEdge源代码3.1-1如下所示:

package edu.princeton.cs.algs4;
/***  有向边*/public class DirectedEdge { /*** 边的起点*/private final int v;/*** 边的终点*/  private final int w;/*** 边的权重*/  private final double weight;/*** 初始化权重weight,从顶点v指向w的有向边* @param v 边的起点* @param w 边的终点* @param weight 边的权重*/public DirectedEdge(int v, int w, double weight) {if (v < 0) throw new IllegalArgumentException("Vertex names must be non-negative integers");if (w < 0) throw new IllegalArgumentException("Vertex names must be non-negative integers");if (Double.isNaN(weight)) throw new IllegalArgumentException("Weight is NaN");this.v = v;this.w = w;this.weight = weight;}/*** 返回边的起点* @return 边的起点*/public int from() {return v;}/*** 边的终点* @return 边的终点*/public int to() {return w;}/*** 边的权重* @return 边的权重 */public double weight() {return weight;}/*** 边的字符串表示* @return 边的字符串表示*/public String toString() {return v + "->" + w + " " + String.format("%5.2f", weight);}
}

3.2 加权有向图

加权有向图API如下表3.2-1所示:

public classEdgeWeightedDigraph
publicEdgeWeightedDigraph(int V)初始化含有V个顶点的空有向图
publicEdgeWeightedDigraph(In in)从输入流读取取构造加权有向图
public intV()顶点总是
public intE()边的总数
public voidaddEdge(DirectedEdge e)添加一条有向边
public Iterable<DirectedEdge>adj(int v)从v指出的边
public Iterable<DirectedEdge>eges()该有向图的所有边
public StringtoString加权有向图的字符串表示

加权有向图EdgeWeightedDigraph 源代码3.2-1如下所示:

package edu.princeton.cs.algs4;import java.util.NoSuchElementException;/***  加权有向图*/
public class EdgeWeightedDigraph {private static final String NEWLINE = System.getProperty("line.separator");/*** 顶点总数*/  private final int V;/*** 边的总数*/  private int E;/*** 顶点指出的边*/  private Bag<DirectedEdge>[] adj;/*** 入度*/  private int[] indegree;/*** 初始化V个顶点的空有向图** @param  V 顶点数*/public EdgeWeightedDigraph(int V) {if (V < 0) throw new IllegalArgumentException("Number of vertices in a Digraph must be non-negative");this.V = V;this.E = 0;this.indegree = new int[V];adj = (Bag<DirectedEdge>[]) new Bag[V];for (int v = 0; v < V; v++)adj[v] = new Bag<DirectedEdge>();}/*** 初始化v个顶点e条边的加权有向图** @param  顶点总是* @param  边的总数*/public EdgeWeightedDigraph(int V, int E) {this(V);if (E < 0) throw new IllegalArgumentException("Number of edges in a Digraph must be non-negative");for (int i = 0; i < E; i++) {int v = StdRandom.uniform(V);int w = StdRandom.uniform(V);double weight = 0.01 * StdRandom.uniform(100);DirectedEdge e = new DirectedEdge(v, w, weight);addEdge(e);}}/**  * 从输入流读取数据初始化加权有向图** @param  输入流*/public EdgeWeightedDigraph(In in) {if (in == null) throw new IllegalArgumentException("argument is null");try {this.V = in.readInt();if (V < 0) throw new IllegalArgumentException("number of vertices in a Digraph must be non-negative");indegree = new int[V];adj = (Bag<DirectedEdge>[]) new Bag[V];for (int v = 0; v < V; v++) {adj[v] = new Bag<DirectedEdge>();}int E = in.readInt();if (E < 0) throw new IllegalArgumentException("Number of edges must be non-negative");for (int i = 0; i < E; i++) {int v = in.readInt();int w = in.readInt();validateVertex(v);validateVertex(w);double weight = in.readDouble();addEdge(new DirectedEdge(v, w, weight));}}   catch (NoSuchElementException e) {throw new IllegalArgumentException("invalid input format in EdgeWeightedDigraph constructor", e);}}/*** 用一个加权有向图初始化加权有向图** @param  加权有向图G*/public EdgeWeightedDigraph(EdgeWeightedDigraph G) {this(G.V());this.E = G.E();for (int v = 0; v < G.V(); v++)this.indegree[v] = G.indegree(v);for (int v = 0; v < G.V(); v++) {// reverse so that adjacency list is in same order as originalStack<DirectedEdge> reverse = new Stack<DirectedEdge>();for (DirectedEdge e : G.adj[v]) {reverse.push(e);}for (DirectedEdge e : reverse) {adj[v].add(e);}}}/*** 顶点总数** @return 顶点总是*/public int V() {return V;}/*** 边的总数** @return 边的总数*/public int E() {return E;}/*** 校验顶点v*/private void validateVertex(int v) {if (v < 0 || v >= V)throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));}/*** 添加一条有向边e** @param  e 有向边e*/public void addEdge(DirectedEdge e) {int v = e.from();int w = e.to();validateVertex(v);validateVertex(w);adj[v].add(e);indegree[w]++;E++;}/*** 顶点v的指出边** @param  v 顶点v* @return 顶点v指出的边*/public Iterable<DirectedEdge> adj(int v) {validateVertex(v);return adj[v];}/*** 顶点v的出度** @param  v 顶点v* @return 顶点v的出度*/public int outdegree(int v) {validateVertex(v);return adj[v].size();}/*** 顶点v的入度** @param  v 顶点v* @return 顶点v的入度*/public int indegree(int v) {validateVertex(v);return indegree[v];}/*** 所有边** @return 所有边*/public Iterable<DirectedEdge> edges() {Bag<DirectedEdge> list = new Bag<DirectedEdge>();for (int v = 0; v < V; v++) {for (DirectedEdge e : adj(v)) {list.add(e);}}return list;} /*** 加权有向图的字符串表示* @return 加权有向图的字符串表示*/public String toString() {StringBuilder s = new StringBuilder();s.append(V + " " + E + NEWLINE);for (int v = 0; v < V; v++) {s.append(v + ": ");for (DirectedEdge e : adj[v]) {s.append(e + "  ");}s.append(NEWLINE);}return s.toString();}
}

加权有向图示意图3.2-1如下所示:

在这里插入图片描述

4 最短路径

4.1 最短路径API

public classSP
publicSP(EdgeWeightedDigraph G, int s)构造函数
public doubledistTo(int v)从顶点s到顶点v的距离,不存在路径为无穷大
public booleanhasPathTo(int v)是否存在从顶点s到v的路径
public Iterable<DirectedEdge>pathTo(int v)从顶点s到v的路径,不存在为null

4.2 最短路径的数据结构

表示最短路径 所需的数据结构很简单,如下图4.2-1所示:

在这里插入图片描述

  • 最短路径树中的边。使用一个由顶点索引的DirectedEdge对象的父链接数组edgeTo[],其中edgeTo[v]的值为连接v和它的父结点的边。
  • 到达起点的距离。由顶点索引的distTo[],其中distTo[v]表示从起点s到v的已知最短路径的长度。

我们约定edgeTo[s]为null,distTo[s]值为0。同时约定,从起点到不可达到顶点的距离均为Double.POSITIVE_INFINITY。

4.3 边的松弛

我们的最短路径API的实现都基于一个被称为松弛的操作。

  • 边的松弛。放松边v->w意味着检查从s到w到最短路径是否是先从s到v,然后在由v到w。如果是,则根据这个情况更新数据结构的内容。由v到w到最短路径是distTo[v]与e.weight()之和-如果这个值小于distTo[w],称这条边失效了并将它忽略;如果这个值更新,就更新数据。代码实现4.3-1如下所示:

        private void relax(DirectedEdge e) {int v = e.from(), w = e.to();if (distTo[w] > distTo[v] + e.weight()) {distTo[w] = distTo[v] + e.weight();edgeTo[w] = e;}}
    

如下图4.3-1所示:

在这里插入图片描述

显示的是边的放松操作之后可能出现的两种情况。一种情况边失效(做边的例子),不更新任何数据;另外一种情况是v->w到达w的最短路径(右边的例子),这将会更新edgeTo[w]和distTo[w]。

4.4 顶点的松弛

实际上,实现会放松从一个顶点这出的所有边。从任意distTo[v]为有限值的顶点v指向任意distTo[]为无穷的顶点的边都是有效的。如果v被放松,那么这些有效边都会被添加到edgeTo[]中。某条从起点指出的边将会是第一天被加入edgeTo[]中的边。算法会谨慎选择起点,使得每次顶点松弛操作都能得出到达某个顶点的更短路径,最好逐渐找出到达某个顶点的最短路径。

顶点松弛代码4.4-1如下所示:

private void relax(EdgeWeightedDigraph G, int) {for(DirectedEdge e: G.adj(v)) {int w = e.to();if(distTo[w] > distTo[v]+ e.weight) {distTo[w] = distTo[v] + e.weight;edgeTo[w] = e;}}
}

结语

如果小伙伴什么问题或者指教,欢迎交流。

❓QQ:806797785

⭐️源代码仓库地址:https://gitee.com/gaogzhen/algorithm

参考链接:

[1][美]Robert Sedgewich,[美]Kevin Wayne著;谢路云译.算法:第4版[M].北京:人民邮电出版社,2012.10.p412-419.

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

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

加强人工智能共性技术研发与产业化协同发展

央视网消息&#xff1a;“以5G为代表的新一代信息技术与制造业、交通、旅游等实体经济重要领域深度融合。”4月20日下午&#xff0c;国新办举行一季度工业和信息化发展情况新闻发布会&#xff0c;相关部门负责人在答问时表示&#xff0c;将用好融合应用这把金钥匙&#xff0c;开…

基于matlab仿真相控天线阵列在波束成形MIMO-OFDM系统中的使用

一、前言 本例显示了相控阵在采用波束成形的MIMO-OFDM通信系统中的使用。它使用通信工具箱和相控阵系统工具箱中的组件&#xff0c;对组成发射器和前端接收器组件的辐射元件进行建模&#xff0c;用于MIMO-OFDM通信系统。使用用户指定的参数&#xff0c;您可以根据不同空间位置和…

JAVA Future类详解及Thread线程是如何运行Future类的

一、Future基本介绍 Future(java.util.concurrent Interface Future<V>)表示异步计算的结果。Future接口提供了检查计算是否完成、检查计算是否被取消、等待计算完成并获取计算结果等方法。 在并发编程中&#xff0c;我们经常用到非阻塞的模型&#xff0c;但继承thread类…

202303-1 田地丈量

代码 #include<iostream> #include<vector> #include<string> #include<cmath> #include<algorithm> #include<stack> using namespace std; int n, a, b;int main() {cin >> n >> a >> b;int x1, y1, x2, y2;int x, y;…

网络基础之网络传输基本流程

网络基础 此小节介绍网络基础概念 首先要明确的是 网络是层状结构&#xff01;分层->OP->解耦 网络发展&#xff1a;最早的时候&#xff0c;每台计算机之间是相互独立的。后续发展到网络互联&#xff0c;就是将多台计算机连接在一起&#xff0c;完成数据共享。 协议&…

19.Java文件操作---I/O流

Java文件操作—I/O流 流(stream)的概念源于UNIX中管道(pipe)的概念。在UNIX中&#xff0c;管道是一条不间断的字节流&#xff0c;用来实现程序或进程间的通信&#xff0c;或读写外围设备、外部文件等。一个流&#xff0c;必有源端和目的端&#xff0c;它们可以是计算机内存的某…

【问题记录】docker 搭建 minio

一、搭建过程 docker 搜索minio镜像 docker search miniodocker 拉取镜像 docker pull minio/miniodocker 启动 minio docker run -p 9900:9900 --name minio -d --restartalways -e MINIO_ACCESS_KEYminio -e MINIO_SECRET_KEY1qazWSX -v /usr/local/minio/data:/data -v …

PHP入门【1】环境搭建

目录 一&#xff0c;安装appserv组合包 二&#xff0c;运行第一个php程序 一&#xff0c;安装appserv组合包 组合包&#xff1a;将apache&#xff0c;mysql&#xff0c;php等服务器软件和工具安装配置完成后打包处理 组合包大大提高了我们的效率&#xff0c;不需要为配置环境…

MACH SYSTEMS操作手册 SAEJ2716(SENT) to RS-232/CAN Gateway怎么使用?

双通道SAE J2716 (SENT)至RS-232/CAN总线网关&#xff0c;具有两个双向SENT通道和RS-232 (SENT-RS232) 或CAN总线 (SENT-CAN) 接口。两种变体还提供两个模拟输出&#xff0c;可以直接将输入SENT数据转换为模拟电压。该网关配备了一个免费的PC应用程序&#xff0c;用于SENT通信分…

Linux Ansible创建任务并执行

目录 通过add-hoc执行anbise任务 通过Playbook剧本方式执行任务 Playbook包含的常用对象 Yaml语法 对Yaml格式自动对齐 Playbook语法检测与执行 Playbook任务实施 Playbook特权升级 Playbook常用模块 软件包管理模块 用户管理模块 存储模块管理 文件操作相关模块 …

gpt在线使用-免费的 GPT在哪下载

免费的 GPT&#xff08;Generative Pre-trained Transformer&#xff09; 。现在您可以免费体验我们的 GPT 技术&#xff0c;来让您的业务或项目更加智能。 GPT 是一种基于最前沿的自然语言处理技术&#xff0c;它展现出了令人惊叹的预测能力和交互性能。我们的 GPT 是在世界顶…

TryHackMe-M4tr1x: Exit Denied(boot2root)

M4tr1x: Exit Denied 大多数人只看到一个完美构建的系统。但你一直都是不同的。你不仅看到表面上的东西&#xff0c;还看到 它下面有什么统治;调节和调节的内部关联机制 几乎完美地管理其每个模块&#xff0c;以至于它试图隐藏所有模块 其多面设计中的微小孔。但是&#xff0c…

linux-01-基础回顾-虚拟机安装linux(centos7)、linux常用命令

文章目录 Linux-Day01课程内容1. 前言1.1 什么是Linux1.2 为什么要学Linux1.3 学完Linux能干什么 2. Linux简介2.1 主流操作系统2.2 Linux发展历史2.3 Linux系统版本 3. Linux安装3.1 安装方式介绍3.2 安装VMware3.3 安装Linux3.4 网卡设置3.5 安装SSH连接工具3.5.1 SSH连接工具…

Linux安装mysql(5.7解压版)

Linux服务器安装软件时&#xff0c;建议安装解压版&#xff0c;将文件安装在自己指定的目录。安装版一般会将软件安装在Linux默认的目录&#xff0c;如/usr/local/&#xff0c;配置文件在/etc/&#xff0c;日志在/logs&#xff0c;安装目录比较分散&#xff0c;特别是不熟悉该软…

Linux网络——PXE高效批量网络装机

Linux网络——PXE高效批量网络装机 一、PXE远程安装服务1.PXE批量部署的优点2.搭建PXE网络体系的安装条件 二、PXE 安装进行前的配置1.PXE装机所需的文件2.搭建 PXE 过程中使用的服务和程序①.DHCP服务②.vsftpd服务③.TFTP服务④.syslinux 三、搭建 PXE 远程安装服务器1.安装相…

IPEmotion 2023 R1支持在线能量分析

新发布的IPEmotion 2023 R1提供了许多新功能&#xff0c;其中最重要的是新的“在线功率计算&#xff08;Online Power Calculation&#xff09;”功能。该功能允许使用预定义的功率计算来进行测量任务和数据分析。此外&#xff0c;IPEmotion 2023 R1现在支持一种新的存储模式&a…

Vmware安装Ubuntu出现 unable to find a medium containing a live file system

一、前言 由于未知的原因&#xff0c;使用Vmware安装Ubuntu的时候&#xff0c;总是遇到奇怪的问题。&#xff08;忘记截图了…&#xff09; 大致是&#xff1a; unable to find a medium containing a live file system找了几个帖子&#xff0c;参考1、参考2&#xff0c;但都…

现场工程师救火-UEFI(BIOS)节能设置导致金牌服务器只跑出龟速

近期协助出现场&#xff0c;解决了一个非常典型的UEFI 启动参数配置不当导致的服务器降效案例。错误的节能参数配置&#xff0c;导致价值几十万的服务器变成龟速服务器&#xff0c;并造成严重的生产事故。 1. 现象 朋友公司近期准备升级2010年就部署的服务器组&#xff0c;新…

【LeetCode】188. 买卖股票的最佳时机 IV

188. 买卖股票的最佳时机 IV&#xff08;困难&#xff09; 思路 状态定义 一、首先确定要一天会有几种状态&#xff0c;不难想到有四种&#xff1a; a.当天买入了股票&#xff1b;b.当天卖出了股票&#xff1b;c.当天没有操作&#xff0c;但是之前是买入股票的状态&#xff…

【数据库】数据库的基础知识

目录 前言 1、 查看数据库 1.1、查看所有数据库&#xff08;show databases;&#xff09; 1.2、创建数据库之后&#xff0c;查看创建的数据库的基本信息。 2、 创建数据库 2.1、直接创建数据库&#xff08;create database [数据库名];&#xff09; 2.2、创建数据库的时…