当前位置: 首页 > news >正文

从有向带权图判断最短路径里各目标顶点顺序

对如下有向带权图,若采用迪杰斯特拉(Dijkstra)算法求从源点a到其他各顶点的最短路径,则得到的第一路径的目标顶点是b,第二条最短路径的目标顶点是c,后续得到的其余各最短路径的目标顶点依次是()

A.d,e,f

B.e,d,f

C.f,d,e

D.f,e,d

首先,先看除了a还有5个顶点,那么就是要走5趟。

在下面表格列出b、c、d、e、f 以及一两三四五趟,最后一行写集合。

顶点一趟两趟三趟四趟五趟
b
c
d
e
f
集合


  1. 在一开始我自己定义:
    1. 顶点a至b算一趟,顶点a至c也算一趟
    2. 以此类推,例如后面讲述的顶点a至b至c算两趟
  2. 然后再看,从a出发,首先接触的是b、c,那么分别写下到b和c的距离。
  3. 其他顶点对a来说一趟接触不到,那么我们就写无穷,即∞。
  4. 其中,(a,b)最短,距离为2,那么得出结论:集合就是{a,b}
  5. 由于顶点c这次没被引用,于是将(a,c)5先搁置至二趟(但每一次搁置到后面一趟需检验a至c是不是最短的,还有没有从a至c更加短的距离,详情看后面几轮)
顶点一趟两趟三趟四趟五趟
b(a,b)2
c(a,c)5(a,c)5
d
e
f
集合{a,b}

  1. 然后再看,从a至b出发,能走两趟的就只有(a,b,c)和(a,b,d),此时(a,b,c)距离为3,(a,b,d)距离为5。
  2. 上一趟的(a,c)搁置到二趟需检验a至c是不是最短的,还有没有从a至c更加短的路线,哦有,就是我们刚才写的(a,b,c),(a,c)距离为5,(a,b,c)距离才3,那么就用(a,b,c)代替(a,c)。
  3. 此时(a,b,c)距离为3,(a,b,d)距离为5
  4. 那么最短的就是(a,b,c)
  5. 那么集合就是{a,b,c}
顶点一趟两趟三趟四趟五趟
b(a,b)2
c(a,c)5(a,c)5/(a,b,c)3
d(a,b,d)5
e
f
集合{a,b}{a,b,c}

 

  1. 然后再看,此时b和c都被引用了,就剩d、e、f,即从a至b至c出发,能走三趟的,能接触到的就是d、e、f
  2. 此时三趟为(a,b,c,d)距离为6,(a,b,c,e)距离为7,(a,b,c,f)距离为4。
  3. (a,b,d)因为上一趟距离长没有选上,虽不是最短,但可以先搁置到这一趟继续写,但搁置到这一趟需检验a至d是不是最短的,还有没有从a至d更加短的路线,哦没有,还是(a,b,d),(a,b,c,d)距离为6,(a,b,d)距离才5,那么就保留(a,b,d)。
  4. 此时三趟为(a,b,d)距离为5,(a,b,c,e)距离为7,(a,b,c,f)距离为4,(a,b,c,f)最短,选(a,b,c,f)。
  5. 故集合为{a,b,c,f}
顶点一趟两趟三趟四趟五趟
b(a,b)2
c(a,c)5(a,c)5/(a,b,c)3
d(a,b,d)5(a,b,d)5/(a,b,c,d)6
e(a,b,c,e)7
f(a,b,c,f)4
集合{a,b}{a,b,c}{a,b,c,f}

  

  1. 然后再看,从a至b至c至f出发,能走四趟的,能接触到的就是d、e
  2. (a,b,d)是从二趟开始搁置到这一趟,因为已经检验过了所以不用检验,而(a,b,c,e)是从三趟才开始搁置的,还没检验过,检验一下,(a,b,c,e)距离为7,(a,b,d,e)距离为6,(a,c,e)距离为9,(a,b,c,d,e)距离为7,故(a,b,d,e)最短,用(a,b,d,e)替代这几个
  3. 然而虽然(a,b,d,e)距离为6,(a,b,d)5距离为5而已,故还是选(a,b,d)。
  4. 故集合为{a,b,c,f,d}
顶点一趟两趟三趟四趟五趟
b(a,b)2
c(a,c)5(a,c)5/(a,b,c)3
d(a,b,d)5(a,b,d)5/(a,b,c,d)6(a,b,d)5
e(a,b,c,e)7(a,b,c,e)7/(a,b,d,e)6/(a,c,e)9/(a,b,c,d,e)7
f(a,b,c,f)4
集合{a,b}{a,b,c}{a,b,c,f}{a,b,c,f,d}


 

  1. 然后再看,此时就剩e,即从a至b至c至f至d出发,能走五趟的,能接触到的就只有e了
  2. (a,b,d,e)是从四趟开始搁置到这一趟,因为已经检验过了所以不用检验。
  3. 故集合为{a,b,c,f,d,e}
顶点一趟两趟三趟四趟五趟
b(a,b)2
c(a,c)5(a,c)5/(a,b,c)3
d(a,b,d)5(a,b,d)5/(a,b,c,d)6(a,b,d)5
e(a,b,c,e)7(a,b,c,e)7/(a,b,d,e)6/(a,c,e)9/(a,b,c,d,e)7(a,b,d,e)6
f(a,b,c,f)4
集合{a,b}{a,b,c}{a,b,c,f}{a,b,c,f,d}{a,b,c,f,d,e}

故后续得到的其余各最短路径的目标顶点依次是{a,b,c,f,d,e}

相关文章:

从有向带权图判断最短路径里各目标顶点顺序

对如下有向带权图,若采用迪杰斯特拉(Dijkstra)算法求从源点a到其他各顶点的最短路径,则得到的第一路径的目标顶点是b,第二条最短路径的目标顶点是c,后续得到的其余各最短路径的目标顶点依次是() A.d,e,f B.e,d,f C.f,d,e D.f,…...

鼠标驱动框架:模拟键盘按键

/* 参考: drivers\hid\usbhid\usbmouse.c */ #include <linux/kernel.h> #include <linux/slab.h> #include <linux/module.h> #include <linux/init.h> #include <linux/usb.h> #include <linux/input.h> #include <linux/hid.h>st…...

ES6之Promise的链式调用

✨ 专栏介绍 在现代Web开发中&#xff0c;JavaScript已经成为了不可或缺的一部分。它不仅可以为网页增加交互性和动态性&#xff0c;还可以在后端开发中使用Node.js构建高效的服务器端应用程序。作为一种灵活且易学的脚本语言&#xff0c;JavaScript具有广泛的应用场景&#x…...

HTML----JavaScript操作对象BOM对象

文章目录 目录 文章目录 本章要求 一.BOM模型概述 二.BOM核心&#xff1a;window对象 常用属性 常用方法&#xff1a; confirm() 案例 open ()close()案例 setTimeout( ) 案例 setInterval( ) 案例 document对象 练习 本章要求 了解BOM模型掌握BOM模型实际应用 一.BOM模型…...

隆道数智大会回顾|第13期《如何构建绿色产业供应链新生态》(完)

本期演讲嘉宾&#xff1a; 史文月 采购与供应链专家 邢庆峰 品类管理和质量管理专家 刘婷婷 中兴通讯供应链规划总监 张燕华 正大生物CIO 吴树贵 隆道公司总裁 本期演讲主题&#xff1a; 如何构建绿色产业供应链新生态 本期内容要点&#xff1a; 1.供应链管理的核心问…...

粒子群优化pso结合bp神经网络优化对csv文件预测matlab(3)

1.csv数据为密西西比数据集&#xff0c;获取数据集可以管我要&#xff0c;数据集内容形式如下图&#xff1a; 2.代码 这里参考的是b站的一位博主。 数据集导入教程在我的另一篇文章bp写过&#xff0c;需要的话可以去看一下 psobp.m close all clc%读取数据 inputX; outputY;…...

软性演员-评论家算法 SAC

软性演员-评论家算法 SAC 软性演员-评论家算法 SAC优势原理软性选择模型结构目标函数重参数化熵正则化代码实现 软性演员-评论家算法 SAC 优势原理 DDPG 的问题在于&#xff0c;训练不稳定、收敛差、依赖超参数、不适应复杂环境。 软性演员-评论家算法 SAC&#xff0c;更稳定…...

Nginx多域名部署多站点

目录 1.修改配置文件nginx.conf 2. 修改hosts文件 1.修改配置文件nginx.conf 在配置文件的 server_name 处修改成自己需要的域名&#xff0c;然后保存退出 j 查看语法是否错误&#xff0c;然后重启nginx nginx -t # 查看语法是否正确 systemctl restart nginx # 重启nginx …...

Java的常规面试题

Java的面试题主要涉及Java基础知识、并发编程、集合原理、JVM原理、I/O与网络编程、设计模式、互联网常用框架等多个领域[6]。一些常见的面试问题包括&#xff1a; 1. 面向对象的特征&#xff1a;继承、封装和多态性。 2. 访问修饰符public、private、protected以及默认时的区别…...

大数据技术发展史

文章目录 Google论文HadoopHive大数据生态 Google论文 今天我们常说的大数据技术&#xff0c;其实起源于Google在2004年前后发表的三篇论文&#xff0c;也就是我们经常听到的“三驾马车”&#xff0c;分别是分布式文件系统GFS、大数据分布式计算框架MapReduce和NoSQL数据库系统…...

linux常见基础指令

入门常见基础指令 ls、stat、 pwd 、cd、tree、 whoami、 touch、 mkdir、 rm 、 man、 cp、mv、cat、tac、echo、>、 >>、 < 、more、 less、 head、 tail、date、 cal、 find、 which、alias、whereis、grep、zip与unzip、 tar、bc、uname、xargs... 热键Tab、…...

“人家赚那么多”系列01:如何练习?练什么?

01 如何练习&#xff1f;练习什么&#xff1f; 今年计划重点围绕「在不骗自己的前提下&#xff0c;如何才能把事儿彻底做好&#xff0c;并做得有声有色&#xff1f;」为主题来写点儿东西&#xff0c;聊聊我是怎么做的&#xff0c;如何通过一些有效的方法来不断优化自己的。 想把…...

【Android】使用android studio查看内置数据库信息

要使用Android Studio查看内置数据库信息&#xff0c;可以按照以下步骤进行操作&#xff1a; 打开Android Studio并打开你的项目。 在左侧的Project窗口中&#xff0c;找到并展开你的app模块。 找到并展开"app" > "src" > "main"文件夹。…...

PHP开发日志 ━━ 基于PHP和JS的AES相互加密解密方法详解(CryptoJS) 适合CryptoJS4.0和PHP8.0

最近客户在做安全等保&#xff0c;需要后台登录密码采用加密方式&#xff0c;原来用个base64变形一下就算了&#xff0c;现在不行&#xff0c;一定要加密加key加盐~~ 前端使用Cypto-JS加密&#xff0c;传输给后端使用PHP解密&#xff0c;当然&#xff0c;前端虽然有key有盐&…...

2021-01-03 excel实现列递增,行保持不变

需求&#xff1a;excel文档数据操作的时候发现自动递增只能实现列不变行号递增 我这里里需要的是列递增行不变 解决方式&#xff1a;通过一些函数的组合使用 INDIRECT("驻场明细!"&CHAR(ROW()62)&ROW(驻场明细!A$28)) INDIRECT()函数的使用&#xff1a; INDI…...

[Python]两个杯子取水问题

利用两个杯子巧取三升水&#xff1a; 今天的这个趣味数学小游戏是利用两个没有刻度的水杯&#xff0c;巧妙地取出三升水来。 题目的条件是&#xff1a;一个总容量为6升的杯子和一个总容量为5升的杯子&#xff0c;同时面前有无限容量的水供你使用。不借助其它任何的容器&#xf…...

C++汇编语言学习计划

前几天买了某游戏的外挂&#xff0c;感觉外挂在我计算机上进行了不少操作&#xff0c;我想一探究竟&#xff0c;可是只有exe&#xff0c;没办法&#xff0c;翻译成汇编我也看不懂&#xff0c;索性来简单学习下。访问Chatgpt4&#xff0c;给了如下学习计划。 要从零开始学习C生成…...

微信服务号升级订阅号条件

服务号和订阅号有什么区别&#xff1f;服务号转为订阅号有哪些作用&#xff1f;首先我们要看一下服务号和订阅号的主要区别。1、服务号推送的消息没有折叠&#xff0c;消息出现在聊天列表中&#xff0c;会像收到消息一样有提醒。而订阅号推送的消息是折叠的&#xff0c;“订阅号…...

SpringBoot整合mybatis多数据源

废话不多说先上结果 对应数据库 首先导入所需的mybatis、mysql和lombok依赖 <dependency><groupId>org.mybatis.spring.boot</groupId><artifactId>mybatis-spring-boot-starter</artifactId><version>2.2.2</version></dependen…...

垃圾收集器与内存分配策略

内存分配和回收原则 对象优先在Eden区分配 大对象直接进入老年代 长期存活的对象进入老年代 什么是内存泄漏 不再使用的对象在系统中未被回收&#xff0c;内存泄漏的积累可能会导致内存溢出 自动垃圾回收与手动垃圾回收 自动垃圾回收&#xff1a;由虚拟机来自动回收对象…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...