图论14-最短路径-Dijkstra算法+Bellman-Ford算法+Floyed算法

文章目录

  • 0 代码仓库
  • 1 Dijkstra算法
  • 2 Dijkstra算法的实现
    • 2.1 设置距离数组
    • 2.2 找到当前路径的最小值 curdis,及对应的该顶点cur
    • 2.3 更新权重
    • 2.4 其他接口
      • 2.4.1 判断某个顶点的连通性
      • 2.4.2 求源点s到某个顶点的最短路径
  • 3使用优先队列优化-Dijkstra算法
    • 3.1 设计内部类node
    • 3.2 入队
    • 3.3 记录路径
    • 3.4 整体
  • 4 Bellman-Ford算法
    • 4.1 松弛操作
    • 4.2 负权环
    • 4.3 算法思想
    • 4.4 进行V-1次松弛操作
    • 4.5 判断负权环
    • 4.6 整体
  • 5 Floyed算法
    • 5.1 设置记录两点最短距离的数组,并初始化两点之间的距离
    • 5.2 更新两点之间的距离

0 代码仓库

https://github.com/Chufeng-Jiang/Graph-Theory/tree/main/src/Chapter11_Min_Path

1 Dijkstra算法

在这里插入图片描述

2 Dijkstra算法的实现

2.1 设置距离数组

//用于存储从源点到当前节点的距离,并初始化
dis = new int[G.V()];
Arrays.fill(dis, Integer.MAX_VALUE);
dis[s] = 0;

2.2 找到当前路径的最小值 curdis,及对应的该顶点cur

int cur = -1, curdis = Integer.MAX_VALUE;

for(int v = 0; v < G.V(); v ++)
    if(!visited[v] && dis[v] < curdis){
        curdis = dis[v];
        cur = v;
    }

2.3 更新权重

visited[cur] = true;
for(int w: G.adj(cur))
   if(!visited[w]){
       if(dis[cur] + G.getWeight(cur, w) < dis[w])
           dis[w] = dis[cur] + G.getWeight(cur, w);
   }

2.4 其他接口

2.4.1 判断某个顶点的连通性

public boolean isConnectedTo(int v){
    G.validateVertex(v);
    return visited[v];
}

2.4.2 求源点s到某个顶点的最短路径

public int distTo(int v){
    G.validateVertex(v);
    return dis[v];
}

在这里插入图片描述

3使用优先队列优化-Dijkstra算法

3.1 设计内部类node

存放节点编号和距离

    private class Node implements Comparable<Node>{

        public int v, dis;

        public Node(int v, int dis){
            this.v = v;
            this.dis = dis;
        }

        @Override
        public int compareTo(Node another){
            return dis - another.dis;
        }
    }

3.2 入队

PriorityQueue<Node> pq = new PriorityQueue<Node>();

pq.add(new Node(s, 0));

这里的缺点就是,更新node时候,会重复添加节点相同的node,但是路径值不一样。不影响最后结果。

while(!pq.isEmpty()){

    int cur = pq.remove().v;
    if(visited[cur]) continue;

    visited[cur] = true;
    for(int w: G.adj(cur))
        if(!visited[w]){
            if(dis[cur] + G.getWeight(cur, w) < dis[w]){
                dis[w] = dis[cur] + G.getWeight(cur, w);
                pq.add(new Node(w, dis[w]));
                pre[w] = cur;
            }
        }
}

3.3 记录路径

private int[] pre;
  • 更新pre数组
for(int w: G.adj(cur))
    if(!visited[w]){
        if(dis[cur] + G.getWeight(cur, w) < dis[w]){
            dis[w] = dis[cur] + G.getWeight(cur, w);
            pq.add(new Node(w, dis[w]));
            pre[w] = cur;
        }
    }
  • 输出路径
    public Iterable<Integer> path(int t){

        ArrayList<Integer> res = new ArrayList<>();
        if(!isConnectedTo(t)) return res;

        int cur = t;
        while(cur != s){
            res.add(cur);
            cur = pre[cur];
        }
        res.add(s);

        Collections.reverse(res);
        return res;
    }

3.4 整体

package Chapter11_Min_Path.Dijkstra_pq;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;


public class Dijkstra {

    private WeightedGraph G;
    private int s;
    private int[] dis;
    private boolean[] visited;
    private int[] pre;

    private class Node implements Comparable<Node>{

        public int v, dis;

        public Node(int v, int dis){
            this.v = v;
            this.dis = dis;
        }

        @Override
        public int compareTo(Node another){
            return dis - another.dis;
        }
    }

    public Dijkstra(WeightedGraph G, int s){

        this.G = G;

        G.validateVertex(s);
        this.s = s;

        dis = new int[G.V()];
        Arrays.fill(dis, Integer.MAX_VALUE);

        pre = new int[G.V()];
        Arrays.fill(pre, -1);

        dis[s] = 0;
        pre[s] = s;
        visited = new boolean[G.V()];

        PriorityQueue<Node> pq = new PriorityQueue<Node>();
        pq.add(new Node(s, 0));

        while(!pq.isEmpty()){

            int cur = pq.remove().v;
            if(visited[cur]) continue;

            visited[cur] = true;
            for(int w: G.adj(cur))
                if(!visited[w]){
                    if(dis[cur] + G.getWeight(cur, w) < dis[w]){
                        dis[w] = dis[cur] + G.getWeight(cur, w);
                        pq.add(new Node(w, dis[w]));
                        pre[w] = cur;
                    }
                }
        }
    }

    public boolean isConnectedTo(int v){

        G.validateVertex(v);
        return visited[v];
    }

    public int distTo(int v){

        G.validateVertex(v);
        return dis[v];
    }

    public Iterable<Integer> path(int t){

        ArrayList<Integer> res = new ArrayList<>();
        if(!isConnectedTo(t)) return res;

        int cur = t;
        while(cur != s){
            res.add(cur);
            cur = pre[cur];
        }
        res.add(s);

        Collections.reverse(res);
        return res;
    }

    static public void main(String[] args){

        WeightedGraph g = new WeightedGraph("g.txt");
        Dijkstra dij = new Dijkstra(g, 0);
        for(int v = 0; v < g.V(); v ++)
            System.out.print(dij.distTo(v) + " ");
        System.out.println();

        System.out.println(dij.path(3));
    }
}

4 Bellman-Ford算法

4.1 松弛操作

在这里插入图片描述

4.2 负权环

在这里插入图片描述

4.3 算法思想

在这里插入图片描述

4.4 进行V-1次松弛操作

// 进行V-1次松弛操作
for(int pass = 1; pass < G.V(); pass ++){
    for(int v = 0; v < G.V(); v ++)
        for(int w: G.adj(v))
            if(dis[v] != Integer.MAX_VALUE && // 避免对无穷值的点进行松弛操作
               dis[v] + G.getWeight(v, w) < dis[w]){
                dis[w] = dis[v] + G.getWeight(v, w);
                pre[w] = v;
            }
}

4.5 判断负权环

// 多进行一次操作,如果还有更新,那么存在负权换
for(int v = 0; v < G.V(); v ++)
    for(int w : G.adj(v))
        if(dis[v] != Integer.MAX_VALUE &&
           dis[v] + G.getWeight(v, w) < dis[w])
            hasNegCycle = true;

4.6 整体

package Chapter11_Min_Path.BellmanFord;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class BellmanFord {

    private WeightedGraph G;
    private int s;
    private int[] dis;
    private int[] pre;
    private boolean hasNegCycle = false;

    public BellmanFord(WeightedGraph G, int s){

        this.G = G;

        G.validateVertex(s);
        this.s = s;

        dis = new int[G.V()];
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[s] = 0;

        pre = new int[G.V()];
        Arrays.fill(pre, -1);

        // 进行V-1次松弛操作
        for(int pass = 1; pass < G.V(); pass ++){
            for(int v = 0; v < G.V(); v ++)
                for(int w: G.adj(v))
                    if(dis[v] != Integer.MAX_VALUE && // 避免对无穷值的点进行松弛操作
                       dis[v] + G.getWeight(v, w) < dis[w]){
                        dis[w] = dis[v] + G.getWeight(v, w);
                        pre[w] = v;
                    }
        }

        // 多进行一次操作,如果还有更新,那么存在负权换
        for(int v = 0; v < G.V(); v ++)
            for(int w : G.adj(v))
                if(dis[v] != Integer.MAX_VALUE &&
                   dis[v] + G.getWeight(v, w) < dis[w])
                    hasNegCycle = true;
    }

    public boolean hasNegativeCycle(){
        return hasNegCycle;
    }

    public boolean isConnectedTo(int v){
        G.validateVertex(v);
        return dis[v] != Integer.MAX_VALUE;
    }

    public int distTo(int v){
        G.validateVertex(v);
        if(hasNegCycle) throw new RuntimeException("exist negative cycle.");
        return dis[v];
    }

    public Iterable<Integer> path(int t){

        ArrayList<Integer> res = new ArrayList<Integer>();
        if(!isConnectedTo(t)) return res;

        int cur = t;
        while(cur != s){
            res.add(cur);
            cur = pre[cur];
        }
        res.add(s);

        Collections.reverse(res);
        return res;
    }

    static public void main(String[] args){

        WeightedGraph g = new WeightedGraph("gw2.txt");
        BellmanFord bf = new BellmanFord(g, 0);
        if(!bf.hasNegativeCycle()){
            for(int v = 0; v < g.V(); v ++)
                System.out.print(bf.distTo(v) + " ");
            System.out.println();

            System.out.println(bf.path(3));
        }
        else
            System.out.println("exist negative cycle.");

        WeightedGraph g2 = new WeightedGraph("g2.txt");
        BellmanFord bf2 = new BellmanFord(g2, 0);
        if(!bf2.hasNegativeCycle()){
            for(int v = 0; v < g2.V(); v ++)
                System.out.print(bf2.distTo(v) + " ");
            System.out.println();
        }
        else
            System.out.println("exist negative cycle.");
    }
}

5 Floyed算法

在这里插入图片描述

5.1 设置记录两点最短距离的数组,并初始化两点之间的距离

private int[][] dis;
  • 初始化两点之间的距离
for(int v = 0; v < G.V(); v ++){
    dis[v][v] = 0;
    for(int w: G.adj(v))
        dis[v][w] = G.getWeight(v, w);
}

5.2 更新两点之间的距离

第一重循环:测试两点之间经过点t是否存在更短的路径。

        for(int t = 0; t < G.V(); t ++)
        
            for(int v = 0; v < G.V(); v ++)
                for(int w = 0; w < G.V(); w ++)
                    if(dis[v][t] != Integer.MAX_VALUE && dis[t][w] != Integer.MAX_VALUE
                       && dis[v][t] + dis[t][w] < dis[v][w])
                        dis[v][w] = dis[v][t] + dis[t][w];

在这里插入图片描述
在这里插入图片描述

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

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

相关文章

CPD:使用restAPI和cpd-cli命令创建DMC实例

环境 Red Hat Enterprise Linux release 8.6 (Ootpa)OCP 4.12.22IBM CP4D 4.8.0Data Management Console 3.1.12 (DMC for CPD 4.8.0) 注&#xff1a;使用了fyre VM。 创建DMC实例 准备 首先export环境变量&#xff1a; . ./stg_env.sh把 cpd-cli 放到PATH里。编辑 ~/.ba…

从GPT定制到Turbo升级再到Assistants API,未来AI世界,你准备好了吗?

引言 在OpenAI DevDay发布会上&#xff0c;OpenAI再次震撼整个人工智能行业&#xff0c;为AI领域带来了重大的更新。CEO Sam Altman宣布推出了定制版本的ChatGPT&#xff0c;这意味着用户现在可以根据自己的需求打造个性化的GPT&#xff0c;并分享至GPT Store。这一消息对于受A…

iText v1.8.1(OCR截图文字识别工具)

iText for mac是一款OCR&#xff08;光学字符识别&#xff09;工具&#xff0c;可以从图片中识别文字&#xff0c;适用于从扫描版的PDF等任意图片中提取文字。 使用iText&#xff0c;您可以方便快捷地从图片中摘抄和批注文字&#xff0c;满足您的各种需求。其自带截图功能&…

基于果蝇算法优化概率神经网络PNN的分类预测 - 附代码

基于果蝇算法优化概率神经网络PNN的分类预测 - 附代码 文章目录 基于果蝇算法优化概率神经网络PNN的分类预测 - 附代码1.PNN网络概述2.变压器故障诊街系统相关背景2.1 模型建立 3.基于果蝇优化的PNN网络5.测试结果6.参考文献7.Matlab代码 摘要&#xff1a;针对PNN神经网络的光滑…

upload-labs关卡5(点和空格绕过)通关思路

文章目录 前言一、回顾上一关知识点二、靶场第五关通关思路1.看源代码2.点和空格绕过3、验证上传 总结 前言 此文章只用于学习和反思巩固文件上传漏洞知识&#xff0c;禁止用于做非法攻击。注意靶场是可以练习的平台&#xff0c;不能随意去尚未授权的网站做渗透测试&#xff0…

Unity中雾效的实现方法二

文章目录 前言一、声明雾效所需要的内置变体二、在 v2f 中声明顶点传入片段中的雾效插值器三、 在顶点着色器中计算雾效采样四、在片元着色器中进行雾效颜色混合在这里插入图片描述 五、最终效果 前言 Unity中雾效的实现方法二&#xff0c;使用 Unity 自带的方法实现&#xff…

JVM及其垃圾回收机制(GC)

目录 一.JVM内存区域划分 二.JVM类加载机制 类加载过程 类加载的时机 双亲委派模型 三.JVM垃圾回收机制&#xff08;GC) GC工作过程 1.找到垃圾/判断垃圾 &#xff08;1&#xff09;引用计数【python/PHP】 &#xff08;2&#xff09;可达性分析【Java】 2.对象释放…

shell 语法介绍

大家好&#xff0c;我是蓝胖子&#xff0c;在日常开发中或多或少都会接触到shell脚本&#xff0c;可以说会shell脚本是一位后端开发的基本功&#xff0c;今天我将会花上一篇文章总结下常见的shell的语法&#xff0c;学完本篇&#xff0c;相信简单的shell脚本就能够看懂了&#…

uniapp的实战总结大全

&#x1f642;博主&#xff1a;冰海恋雨 &#x1f642;文章核心&#xff1a;uniapp部分总结 目录 ​编辑 目录 前言&#xff1a; 解决方案 1. 跨平台开发 2. Vue.js生态 3. 组件库 4. 自定义组件 5. Native能力 6. 插件生态 7. 性能优化 写法 1. 模板&#xf…

基于范数求解缩放因子方法的MIMO系统预编码技术matlab仿真

目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 4.1. MIMO系统模型 4.2. 基于范数求解缩放因子的预编码技术 5.算法完整程序工程 1.算法运行效果图预览 2.算法运行软件版本 MATLAB2022A 3.部分核心程序 。。。。。。。。。。。。。。。…

Hbuilder介绍,uniapp框架

Hbuilder对程序前端页面进行开发&#xff08;包括android&#xff0c;ios&#xff0c;小程序&#xff0c;web等等&#xff09;,其实也就是相当于把android开发进行前后端分离了。方便分工协作。提高开发效率。 用前端框架开发可以实现一次编码&#xff0c;多平台运行。 &…

人工智能极简史:一文读懂ChatGPT的前世今生

2022年11月30日&#xff0c;OpenAI推出的一款人工智能技术驱动的自然语言处理工具——ChatGPT&#xff0c;迅速在社交媒体上走红&#xff0c;短短5天&#xff0c;注册用户数就超过100万。 2023年1月末&#xff0c;ChatGPT的月活用户已突破1亿&#xff0c;一度成为史上增长最快的…

网站定制开发的流程|软件app小程序开发定制

网站定制开发的流程|软件app小程序开发定制 网站定制开发是一个为个体或企业创建定制化网站的过程。它涉及到规划、设计、开发和测试等一系列步骤&#xff0c;以满足客户的需求和目标。下面是网站定制开发的基本流程。 1. 需求分析&#xff1a;首先&#xff0c;与客户沟通并了解…

Netty Review - 快速上手篇

文章目录 基础概念官网Whats NettyWhy NettyAbout Netty Author & LeaderWhat can Netty doNetty开发流程Flow HL View客户端开发Handler客户端启动类 服务端开发Handler服务器端启动类 运行示例 基础概念 BIO、NIO和AIO这三个概念分别对应三种通讯模型&#xff1a;阻塞、…

Docker 中的端口

Docker 中的端口 0.0.0.0:8080->80/tcp &#xff0c;主机&#xff08;即运行 Docker 的机器&#xff09;监听8080端口&#xff0c;如果有请求转发到容器的 80 端口上去。 详细解释一下&#xff1a; 0.0.0.0:8080->80/tcp &#xff1a;这是一个端口映射规则。 0.0.0.0:80…

【C语言 | 指针】C指针详解(经典,非常详细)

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; &#x1f923;本文内容&#x1f923;&a…

Django下的Race Condition漏洞

目录 环境搭建 无锁无事务的竞争攻击复现 无锁有事务的竞争攻击复现 悲观锁进行防御 乐观锁进行防御 环境搭建 首先我们安装源码包&#xff1a;GitHub - phith0n/race-condition-playground: Playground for Race Condition attack 然后将源码包上传到Ubuntu 为了方便使…

软板当然可以弯折啊,只是容易弯出问题而已

高速先生成员&#xff1a;黄刚 每次在介绍具体案例之前&#xff0c;都还是先铺垫下基础知识吧。今天讲的是一个软板的案例&#xff0c;我们循例先介绍下软板的概念。相信大多数的硬件工程师&#xff0c;PCB设计工程师或者测试工程师都见过&#xff0c;就是像下面的这些了。 它作…

openGauss学习笔记-118 openGauss 数据库管理-设置数据库审计-维护审计日志

文章目录 openGauss学习笔记-118 openGauss 数据库管理-设置数据库审计-维护审计日志118.1 前提条件118.2 背景信息118.3 操作步骤 openGauss学习笔记-118 openGauss 数据库管理-设置数据库审计-维护审计日志 118.1 前提条件 用户必须拥有审计权限。 118.2 背景信息 与审计日…

手写线性表C++ vector

目录 一、vector基本概念 1.1、构造函数 1.2、析构函数 1.3、插入元素 1.4、删除元素 1.5、重载运算符 二、完整代码 一、vector基本概念 C中的vector是一种动态数组&#xff0c;它可以根据需要自动调整大小。vector是C标准模板库&#xff08;STL&#xff09;中的一个容…