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

文章目录

    • 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 original
            Stack<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.

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

LeetCode 27.移除元素

LeetCode 27.移除元素

文章目录 &#x1f4a1;题目分析&#x1f4a1;解题思路&#x1f6a9;思路1:暴力求解 --- 遍历&#x1f514;接口源码&#xff1a;&#x1f6a9;思路2:空间换时间&#x1f514;接口源码&#xff1a;&#x1f6a9;思路3:双指针&#xff08;快慢指针&#xff09;&#x1f514;接口…
阅读更多...
【C++】string类的简单模拟实现

【C++】string类的简单模拟实现

目录 string类初识 string模拟实现 string类成员变量 构造函数 拷贝构造 赋值运算符重载 析构函数 深浅拷贝问题 string类初识 由于C语言中的字符串不太符合OOP(面向对象编程)的思想&#xff0c;而且其底层空间需要用户自己管理&#xff0c;经常有访问越界的情况出现。…
阅读更多...
解决方案：Zotero实现参考文献中英文混排，将英文文献中的“等”转成“et al.”

解决方案：Zotero实现参考文献中英文混排，将英文文献中的“等”转成“et al.”

Zotero 是一款非常实用且易于使用的参考文献管理工具&#xff0c;可帮助用户收集、整理和引用各种类型的文献&#xff0c;包括图书、期刊文章、网页等。在学术写作中起着重要作用。 但是其在中文世界中&#xff0c;运行起来偶尔会出现问题&#xff0c;这里记录一个问题及其解决…
阅读更多...
chmod 命令 (chmod 0660)

chmod 命令 (chmod 0660)

chmod的作用: 用于设置文件所有者和文件关联组的命令,就是控制用户的权限命令 注意事项: chown 需要超级用户 root 的权限才能执行此命令。 自己常用chmod 命令是 chmod 777 * 给所有文件权限 chmod 777 文件名 给单独文件权限 这个777 是怎么来的, 或者chmod 0660 这…
阅读更多...
java 获取时间的方法

java 获取时间的方法

Java的时间是通过字节码指令来控制的&#xff0c;所以 java程序的运行时间是通过字节码指令来控制的。但是由于 Java程序在运行时&#xff0c; JVM会产生一些状态&#xff0c;所以在执行 JVM指令时&#xff0c; JVM也会产生一些状态。 我们在执行 java程序时&#xff0c;主要是…
阅读更多...
kafka延时队列内部应用简介

kafka延时队列内部应用简介

kafka延时队列_悠然予夏的博客-CSDN博客 两个follower副本都已经拉取到了leader副本的最新位置&#xff0c;此时又向leader副本发送拉取请求&#xff0c;而leader副本并没有新的消息写入&#xff0c;那么此时leader副本该如何处理呢&#xff1f;可以直接返回空的拉取结…
阅读更多...
IEEE14节点系统在如短路分析，潮流研究，互连电网中的研究（Simulink）

IEEE14节点系统在如短路分析，潮流研究，互连电网中的研究（Simulink）

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…
阅读更多...
easyrecovery16最新数据恢复软件密钥使用方法教程

easyrecovery16最新数据恢复软件密钥使用方法教程

easyrecovery是一款专业的数据恢复软件,其最新版本为easyrecovery2023将于2022年底发布。总之,easyrecovery是一款功能齐全、性能稳定的专业数据恢复软件,无论删除文件、格式化分区或磁盘故障,它都可以提供最高的恢复成功率。值得个人用户选用。此版本在功能和性能上有较大提升…
阅读更多...
BBR原版/魔改/plus/锐速/七合一脚本linux加速脚本/硬盘挂载/cc防御/宝塔

BBR原版/魔改/plus/锐速/七合一脚本linux加速脚本/硬盘挂载/cc防御/宝塔

BBR原版/魔改/plus/锐速七合一脚本linux加速脚本/硬盘挂载/CC防御/宝塔 新云分享的七合一脚本&#xff0c;包含原版BBR、魔改BBR、bbrplus以及锐速可选。 在vultr上Centos 7, Debian 8/9, Ubuntu 16/18测试通过&#xff0c;不支持ovz。 安装指令&#xff1a;复制下面命令在s…
阅读更多...
基于构效关系模型的药物设计（QSAR）

基于构效关系模型的药物设计（QSAR）

基于构效关系模型的药物设计&#xff08;QSAR&#xff09; 定量构效关系&#xff08;QSAR&#xff0c;Quantitative Structure-Activity Relationship&#xff09;分析是指利用理论计算和统计分析工具来研究系列化合物结构&#xff08;包括二维分子结构、三维分子结构和电子结…
阅读更多...
【Maven 入门】第二章、Maven核心程序解压与配置

【Maven 入门】第二章、Maven核心程序解压与配置

一、Maven 官网地址 首页&#xff1a; Maven – Welcome to Apache Maven(opens new window) 下载页面&#xff1a; Maven – Download Apache Maven(opens new window) 本文以maven-3.3.8为例 具体下载地址&#xff1a;https://dlcdn.apache.org/maven/maven-3/3.8.8/bina…
阅读更多...
【问题记录】docker 搭建 minio

【问题记录】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 …
阅读更多...
vue-cli的使用和单页面应用程序、使用vue-cli脚手架创建vue项目步骤

vue-cli的使用和单页面应用程序、使用vue-cli脚手架创建vue项目步骤

1.vue-cli的使用 vue-cli是Vue.js开发的标准工具。它简化了程序员基于webpack创建工程化的Vue项目的过程。 引用自vue-cli官网上的一句话: 程序员可以专注在撰写应用上&#xff0c;而不必花好几天去纠结webpack配置的问题。 中文官网: https://cli.vuejs.org/zh/ 1.1 安装 …
阅读更多...
8年测开年薪30W，为什么从开发转型为测试？谈谈这些年的心路历程……

8年测开年薪30W，为什么从开发转型为测试？谈谈这些年的心路历程……

谈谈我的以前&#xff0c;从毕业以来从事过两个多月的Oracle开发后转型为软件测试&#xff0c;到现在已近过去8年成长为一个测试开发工程师&#xff0c;总结一下之间的心路历程&#xff0c;希望能给徘徊在开发和测试之前的同学一点小小参考。 一、测试之路伏笔 上学偷懒&#…
阅读更多...
updateByPrimaryKey和updateByPrimaryKeySelective的区别

updateByPrimaryKey和updateByPrimaryKeySelective的区别

版权声明 本文原创作者&#xff1a;谷哥的小弟作者博客地址&#xff1a;http://blog.csdn.net/lfdfhl MyBatis Generator概述 MyBatis Generator是一个专门为MyBatis框架使用者定制的代码生成器&#xff0c;它可以快速的根据表生成对应的映射文件、接口文件、POJO。而且&#…
阅读更多...
哪个品牌的洗地机更好用？热门洗地机盘点

哪个品牌的洗地机更好用？热门洗地机盘点

洗地机没有使用过之前一直怀疑是不是智商税&#xff0c;等到后面体验过之后&#xff0c;发现是真的香。因为不可否认的是&#xff0c;洗地机的清洁力还是不错的。不仅能够快速清洁干净地面&#xff0c;大大的节省了我们的清洁用时&#xff0c;操作起来也省心省力。作为一个洗地…
阅读更多...
Linux下实现C语言程序

Linux下实现C语言程序

一.情况说明 写这篇博客的情况比较复杂&#xff0c;首先我本来是参加新星计划按照规划现在去学习shell脚本语言的&#xff0c;但是博主现在由于其他原因需要了解makefile&#xff0c;makefile是Linux系统下的一种工具&#xff0c;makefile的一些背景要涉及链接库的知识&#xf…
阅读更多...
css初入门：网页布局之网格布局-grid

css初入门：网页布局之网格布局-grid

文章目录 网格布局-grid1、设置网格布局2、网格布局介绍3、网格容器grid-template-columns属性grid-template-rows 属性justify-content 属性justify-items属性align-content 属性 4、网格项目grid-column-start、grid-column-start、grid-column属性grid-row-start、grid-row-…
阅读更多...
4.2.2字符串KMP算法

4.2.2字符串KMP算法

对朴素模式匹配算法的优化&#xff1a; 当我们匹配最后一个字符才发现匹配失败。 那么前面这些字符一定是与模式串对应的。 通过模式串的部分匹配 朴素模式匹配算法优化思路&#xff1a; 不匹配的字符之前&#xff0c;一定是和模式串一致的。 可以跳过中间好几个没有必要的对比…
阅读更多...
如何将项目提交到别人的仓库

如何将项目提交到别人的仓库

大纲&#xff1a; 1、在gitee中克隆(clone)别人仓库的代码。 首先&#xff0c;进入别人的仓库&#xff0c;点击 克隆/下载 2、在你存放项目的文件夹下克隆你刚刚复制的代码 &#xff08;右键点击Git Clone即可&#xff09; 点击OK 就开始克隆了 克隆成功之后&#xff0c;文件上…
阅读更多...
最新文章

Copyright @ 2022~2023