当前位置: 首页 > 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;由虚拟机来自动回收对象…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

基于PHP的连锁酒店管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...