您现在的位置是:首页 > 正文

MIT CS6.006 最短路径专题

2024-02-01 06:42:22阅读 3

单源最短路径
·找出一个带权有向图从起点到终点权重和最小的路径。
几个变体:
1.单目的地最短路径问题
2.单结点对最短路径问题
3.所有节点对最短路径问题

一个隐藏的重要性质:

两个节点之间的一条最短路径也包含着其它的最短路径,也就是说,最短路径的子路径也是最短路径

一般性,我们可以假定找到的最短路径中没有环路,即他们都是简单路径,由于图G=(V, E)中任意无环路径最多包含|V|个不同的节点,所以它至多包含|V-1|条边。因此最短路径至多是|V-1|

松弛操作(relaxation)
对一条边(u, v)的松弛过程为:
1.首先测试从起点s到v的最短路径能否改善
方法:将从节点s到节点u之间的最短路径距离加上节点u于v之间的边权重,并于当前s到v的最短路径估计进行比较,如前者更小就更新。

伪代码:

RELAX(u, v, w)
    if v.d>u.d+w(u, v)
       v.d = u.d + w(u, v)
       v.Π=u

解决单源最短路径的两种算法:
Bellman-Ford:解决一般情况下的单源最短路径(边权重可为负值),动态规划
Dijkstra:只能解决边权值为正的情况,贪心,时间复杂度较低。

Bellman-Ford:

给定带权重的有向图G=(V, E)和权重函数w, Bellman-Ford算法返回一个布尔值,表明是否存在一个从源节点可以到达的权重为负值的环路,如果该环路存在,算法告诉我们不存在解决方法,环路不存在,算法返回最短路径以及对应权重。
时间复杂度O(VE)
伪代码:

BELLMAN-FORD(G, w, s)
   INIIALIZE-SINGLE-SOURCE(G, s)
      for i = 1 to |G.V| - 1
          for each edge(u, v)∈G.E
              RELAX(u, v, w)
      for each edge(u, v)∈G.E
          if v.d>u.d+w(u, v)
             return FLASE
      return TRUE

给定原点是s,初始化时候除了原点s之外,其他的都是无穷大的。因为有5个顶点,所以需要松弛的次数为5-1次在这里插入图片描述

这里我们按照边<t,x>、<t,y>、<t,z>、<y,x>、<y,z>、<z,x>、<z,s>、<s,t>、<s,y>的顺序进行变得松弛操作。第一次按照上述边进行松弛操作之后(实际上只对<s,t>、<s,y>进行操作)的结果为
在这里插入图片描述
第二次按照给定边进行松弛操作之后:
在这里插入图片描述
第三次松弛操作之后:
在这里插入图片描述
最后一次松弛操作:
在这里插入图片描述

#include<iostream>
#include<vector>
#include<cmath>

using namespace std;
struct edge{
   
    int from;
    int to;
    double weight;

网站文章

  • 在ubuntu环境下安装cpu版本的tensorflow

    环境要求:ubuntu14.04 64位、 因为要使用分布式深度学习平台,这里选择了tensorflow,我的电脑是ATI的显卡,所以这里记录的是安装cpu版本的tensorflow,其具体安装过程如下: (1)安装anaconda(这是一个很好的python编程的IDE,具体安装过程请参见其他资料); (2)安装conda环境。好处是conda环境能够把不同的python工程所需的依赖库隔...

    2024-02-01 06:41:51
  • Java接受blob类型图片_原生JS上传图片接收服务器端图片并且显示图片(主要描述blob类型)...

    Java接受blob类型图片_原生JS上传图片接收服务器端图片并且显示图片(主要描述blob类型)...

    1.了解后端处理图像的方式一:图片以独立文件的形式存储在服务器的指定文件夹中,再将路径存入数据库字段中二:将图片转换成blob,直接存储到数据库的 Image 类型字段中(这种方式负担很大不建议使用)...

    2024-02-01 06:41:44
  • startService, bindService区别和总结

    service有2种启动方式,startService和bindService。知识点包括以下几个方面:一. 生命周期 (一) startService生命周期 1. onCreate() –&gt;...

    2024-02-01 06:41:38
  • SpringBoot使用Redis缓存 + @Cacheable, @CachePut, @CacheEvict注解使用

    SpringBoot使用Redis缓存 + @Cacheable, @CachePut, @CacheEvict注解使用

    目录 SpringBoot使用Redis缓存 Spring缓存注解@Cache使用 @Cacheable、@CachePut、@CacheEvict 注释介绍 SpringBoot使用Redis缓存 - gdpuzxs - 博客园 https://www.cnblogs.com/gdpuzxs/p/7222309.html SpringBoot使用Redis...

    2024-02-01 06:41:08
  • AES-128-CBC加解密方法:nodejs加密QT解密(附C语言版加解密全过程)

    服务器端使用的是nodejs编写的代码,对明文进行加密,客户端使用的是QT4.5.3编写代码,调用openssl crypto库函数,对密文进行解密。注意:加解密要对等,即加解密的秘钥相同,向量也要相同,由于是两种不同的语言写的代码,因此两边都要做好一致性检查,比如秘钥的处理,密文的编码方式等等。这里两边都对秘钥进行了MD5加密,并设置向量和秘钥一样(可自由设置秘钥和向量,我们的代码中处理...

    2024-02-01 06:41:02
  • 亿美软通出席硬核桃5G开发者社区周年庆,喜获“金核桃奖”

    亿美软通出席硬核桃5G开发者社区周年庆,喜获“金核桃奖”

    12月15日,亿美软通受邀出席硬核桃5G消息开发者社区周年庆活动。庆典现场,亿美软通CMO张翀对与硬核桃“结缘”一年来亿美在5G消息方面的发展成果做了分享,同时也针对“商用在即,5G消息CSP信息服务...

    2024-02-01 06:40:54
  • 逐行对比LLaMA2和LLaMA模型源代码

    逐行对比LLaMA2和LLaMA模型源代码

    这是因为键和值的数量直接影响了注意力矩阵和值矩阵的大小,如果序列长度非常大,这些矩阵的存储和计算可能会变得非常昂贵。在这种情况下,需要在计算注意力权重前,将键和值的头数通过复制的方式扩展到与查询头数一...

    2024-02-01 06:40:49
  • fork源码分析

    文章目录

    2024-02-01 06:40:24
  • 计算机语言bus代表什么,计算机中bus指什么

    大家好,我是时间财富网智能客服时间君,上述问题将由我为大家进行解答。计算机中bus是指总线,总线的作用就是在计算机各部件之间传递信息,由数据总线,地址总线和控制总线组成。总线(Bus)是计算机各种功能...

    2024-02-01 06:40:17
  • 【漏洞复现】JDWP远程命令执行漏洞

    【漏洞复现】JDWP远程命令执行漏洞

    0x01 漏洞描述JPDA(Java Platform Debugger Architecture):即Java平台调试体系架构。Java虚拟机设计的专门的API接口供调试和监控虚拟机使用JPDA按照...

    2024-02-01 06:40:09