【管理运筹学】第 7 章 | 图与网络分析(3,最短路问题)

这篇具有很好参考价值的文章主要介绍了【管理运筹学】第 7 章 | 图与网络分析(3,最短路问题)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

系列文章目录

【管理运筹学】第 7 章 | 图与网络分析(1,图论背景以及基本概念、术语、矩阵表示)
【管理运筹学】第 7 章 | 图与网络分析(2,最小支撑树问题)
【管理运筹学】第 7 章 | 图与网络分析(4,最大流问题)
【管理运筹学】第 7 章 | 图与网络分析(5,最小费用流问题及最小费用最大流问题)


引言

承接前文,我们来学习图论中另一个经典问题 —— 最短路问题。


三、最短路问题

3.1 最短路问题定义

给定一个赋权有向图 G = ( V , A , W ) G=(V,A,W) G=(V,A,W) ,对每一个弧 a i j = ( v i , v j ) a_{ij}=(v_i,v_j) aij=(vi,vj) ,相应地有权 w ( a i j ) = w i j w(a_{ij})=w_{ij} w(aij)=wij ,又给定 G G G 中两个顶点 v s , v t v_s,v_t vs,vt 。设 P P P G G G v s → v t v_s \to v_t vsvt 的一条路,定义路 P P P 的权是路中所有弧权重之和,记为 W ( P ) W(P) W(P) 。最短路问题就是要在所有 v s → v t v_s \to v_t vsvt 的路中,求取一条权最小的路 P ∗ P^* P ,称其为 v s → v t v_s \to v_t vsvt 的最短路,记为 P ( v s , v t ) P(v_s,v_t) P(vs,vt) 。路 P ∗ P^* P 的权称为 v s → v t v_s \to v_t vsvt 的距离,记为 d ( v s , v t ) d(v_s,v_t) d(vs,vt)

显然, d ( v s , v t ) d(v_s,v_t) d(vs,vt) 不一定等于 d ( v t , v s ) d(v_t,v_s) d(vt,vs) 。我们主要研究有向网络,对于无向网络,每条边可视为双向弧。

3.2 Dijkstra 算法

Dijkstra 算法是 1959 年提出的用于解决非负权网络中寻找一个指定顶点到其他顶点的最短路的最好算法之一。

3.2.1 算法基本依据

Dijkstra 算法的基本思想基于以下三个出发点。

第一,最短路的子路还是最短路。

定理 1 —— 对于弧的权大于 0 的有向网络 G = ( V , A , W ) G=(V,A,W) G=(V,A,W) ,若 P P P G G G 中的一条最短路,则 P P P 的子路也是最短路。

第二,设非负权网络 G = ( V , A , W ) G=(V,A,W) G=(V,A,W) 中, v s v_s vs 到所有其他顶点的最短路长度按大小排列为 d 0 ≤ d 1 ≤ ⋯ ≤ d n d_0 \leq d_1 \leq \dots \leq d_n d0d1dn 。假设 d 1 , d 2 , … , d k d_1,d_2,\dots,d_k d1,d2,,dk 为已求得对应的最短路径分别为 P 1 = P ( v s , v 1 ) , P 2 = ( v s , v 2 ) , … , P k = ( v s , v k ) P_1=P(v_s,v_1),P_2=(v_s,v_2),\dots,P_k=(v_s,v_k) P1=P(vs,v1),P2=(vs,v2),,Pk=(vs,vk) ,并记 S k = { v s , v 1 , … , v k } S_k=\{v_s,v_1,\dots,v_k\} Sk={vs,v1,,vk} ,则 P k P_k Pk 中弧的数目不大于 k k k

第三,最短路的迭代计算公式。

讲实话,硬看公式很头疼,最好结合算例来看,我也就不展示了,后面算法步骤中也会体现。

3.2.2 算法基本思想与步骤

Dijkstra 算法采用标号法,每个顶点有两个标号,一个用于标记路长,用 d ( v i ) d(v_i) d(vi) 表示;另一个用于标记从起点到终点路径的最后一条弧的起始点号(其实就是最短路中终点前一个点)。

网络顶点的标号分两类,一类是永久标号,一类是临时标号。当迭代到第 k k k 步时,获得永久标号的点意味着已经找到 v s v_s vs 到该点的最短路的路长和路径。

将获得永久标号的点放在 S k S_k Sk 集合中,获得永久标号的 d d d 值和 λ \lambda λ 值不再修改。获得临时标号的点(集合 T T T)意味着还没找到最短路。

算法的步骤如下:

第一步: 初始化,令 k = 0 , S 0 = { v s } , T 0 = { v 1 , v 2 , … , v n } , d 0 ( v s ) = 0 , d 0 ( v i ) = ∞ k=0,S^0=\{v_s\},T^0=\{v_1,v_2,\dots,v_n\},d^0(v_s)=0,d^0(v_i)=\infty k=0,S0={vs},T0={v1,v2,,vn},d0(vs)=0,d0(vi)= ,为临时标号值。 λ ( v i ) = v s \lambda(v_i)=v_s λ(vi)=vs ,表示最短路中点 v i v_i vi 的前一个点。 r e s e n t = v s resent=v_s resent=vs ,表示最新获得永久标号的点。

第二步: k = k + 1 k=k+1 k=k+1 ,对于所有临时标号 v l ∈ T k − 1 v_l \in T^{k-1} vlTk1 ,计算: d k ( v l ) = m i n { d k − 1 ( v l ) , d ∗ ( r e s e n t ) + w ( r e s e n t , v l ) } d^k(v_l)=min\{d^{k-1}(v_l),d^*(resent)+w(resent,v_l)\} dk(vl)=min{dk1(vl),d(resent)+w(resent,vl)} 如果 d k ( v l ) < d k − 1 ( v l ) d^k(v_l)<d^{k-1}(v_l) dk(vl)<dk1(vl) ,则 λ k ( v l ) = r e s e n t \lambda^k(v_l)=resent λk(vl)=resent ,否则, λ k ( v l ) = λ k − 1 ( v l ) \lambda^k(v_l)=\lambda^{k-1}(v_l) λk(vl)=λk1(vl)

第三步: v m v_m vm 满足是所有 T T T 标号中最小的,则 r e s e n t = v m , S k = S k − 1 ⋃ { v m } , T k = T k − 1 − { v m } resent=v_m,S^{k}=S^{k-1} \bigcup\{v_m\},T^k=T^{k-1}-\{v_m\} resent=vm,Sk=Sk1{vm},Tk=Tk1{vm} 。若 k = n k=n k=n ,算法结束;否则,转第二步。

Dijkstra 算法结束后, d ∗ d^* d 值即为某点到起点的最短距离,通过每次迭代的 λ ∗ \lambda^* λ 值进行回溯,可得到所有其他点到起点的最短路径。

【管理运筹学】第 7 章 | 图与网络分析(3,最短路问题),# 运筹学,管理运筹学,图论,最短路问题,Dijkstra 算法,逐次逼近算法,Floyd 算法,Bellman-Ford 算法

3.3 逐次逼近算法(Bellman-Ford 算法)

北交大的书上第二个方法写的是 PDM 算法,以前从来没听过,还好看了一下去年大纲,没提到这个,我就不去看了。大纲里还说了一个叫 Ford 算法,网上查了查应该是 Bellman-Ford 算法,但是书上往后面却找不到 Ford 相关字眼,只有一个逐次逼近算法倒还有可能。

于是网上又一顿搜索逐次逼近算法,刚开始也是一点字眼都看不到,后来耐心性子先看了下这个算法的内容,在知乎的一篇文章中看到 Bellman-Ford 算法是基于逐次逼近的思想。两者比对一下,应该北交大书上的逐次逼近算法就是 Bellman-Ford 算法无疑了。

Dijkstra 算法的一个缺点就是,不适用于有负权重的网络,而逐次逼近算法便可以解决这个问题,它适用于有负权但不含负回路的有向赋权图。

逐次逼近算法的基本步骤与思路如下。

第一步:(赋初值) k = 1 k=1 k=1 k k k 为迭代步骤)。 d 1 j 1 = { 0 , v 1 = v j w 1 j , ( v 1 , v j ) ∈ A ∞ , ( v 1 , v j ) ∉ A d^1_{1j}=\begin{cases} 0, & v_1=v_j \\ w_{1j},& (v_1,v_j) \in A\\ \infty,&(v_1,v_j) \notin A \end{cases} d1j1= 0,w1j,,v1=vj(v1,vj)A(v1,vj)/A 对于赋权有向网络 G = ( V , A , W ) G=(V,A,W) G=(V,A,W) v 1 v_1 v1 是指定的起点, d 1 j 1 d^1_{1j} d1j1 的含义是从 v 1 v_1 v1 点到 v j v_j vj 点最多含有一个弧的最短路的路长。

λ 1 j 1 \lambda_{1j}^1 λ1j1 为从 v 1 v_1 v1 点到 v j v_j vj 点最多含有一个弧的最短路的终点 v j v_j vj 的前一个点号。

第二步:递推,第三步:判断。

不是我省懒,实在是要通过具体算例才能看明白,我就不细说了。
而且这个方法有点像是遍历法了,我有点回忆起来当初上系统分析时也讲过这个,不过不是叫这个名。

3.4 Floyd 算法

当我们的需求是任意两点之间的最短路,而不是一点到其他所有点的最短路时,只能考虑重复使用 Dijkstra 算法,依次改变起点。如果此时网络中有负权,可以重复使用逐次逼近法来实现。显然,这样是比较繁琐的,而 Floyd 算法便是可以直接求出任意两点之间的最短路的一种算法,它也适用于含有负权的网络。

具体算法步骤是真不好用文字表达,至少我现在表达不出来,下次找机会出点视频更方便些。


写在最后

算法学习果然是艰辛和耗时的,难怪计算机的出现让图论发展迅速。不过也只有正确掌握算法的基本思想才能正确地用计算机进行辅助计算。

书上的数学描述对于我来说是很抽象的,基本上只能靠算例来加深理解,所以我目前给不了大家一些很通俗的解释,只能到这个水平了。文章来源地址https://www.toymoban.com/news/detail-699007.html

到了这里,关于【管理运筹学】第 7 章 | 图与网络分析(3,最短路问题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 运筹学经典问题(五):多商品流运输问题

    前面介绍了多商品网络流(MCNF)问题,今天要介绍的多商品流运输问题(Mulit-commodity Transportation Problem, MCTP)与MCNF的唯一差异别:MCTP要求商品直接从供应商运送到客户,没有中间流转的路径。 集合: S S S :供应商的集合; C C C :客户的集合; A A A :网络中弧段的集合,

    2024年02月04日
    浏览(51)
  • 【课堂笔记】运筹学第二章:对偶问题

    听说运筹学这门课挺好的,有值得一听的必要;此篇用作课堂总结、期末复习及记录。 或许与教材内容会有很大程度重复。 本章开始会适当结合一些B站网课【运筹学】应试向基础教程 对偶问题的对偶问题就是原问题 矩阵表达 要弄清楚矩阵 A A A 和 C C C 分别是什么 最好记住

    2024年02月07日
    浏览(96)
  • 运筹学—运输问题与表上作业法

    不考虑运价,从西北角的格子开始分配运量,按尽可能满足一方取小的原则,第一行和第一列的格子分配完后,依次向东南角方向的格子进行运量分配。 例如: 第一步:列出产售平衡表 第二步:利用西北角法进行运量分配: 首先在产售平衡表的x 11 处尽可能取最小值:min

    2024年02月12日
    浏览(43)
  • 【管理运筹学】第 8 章 | 动态规划(1,多阶段决策过程与动态规划基本概念)

    【管理运筹学】第 8 章 | 动态规划(1,多阶段决策过程与动态规划基本概念) 【管理运筹学】第 8 章 | 动态规划(2,动态规划的基本思想与模型求解) 【管理运筹学】第 8 章 | 动态规划(3,资源分配问题) 【管理运筹学】第 8 章 | 动态规划(4,生产与储存问题) 【管理

    2024年04月23日
    浏览(43)
  • 运筹学—例题求解

    作答如下:      图解法验证:  由图可得在点x1=20,x2=24取到最大值 Z =4080; 作答如下: 解: (1)设 xij 为从产地Ai运往销地Bj的运输量,得到下列运输量表设 xij 为从产地Ai运往销地Bj的运输量,得到下列运输量表   B1 B2 B3 产量 A1 x 11 x 12 x 13 200 A2 x 21 x 22 x 23 230 销量 100 150 180

    2024年02月04日
    浏览(51)
  • #运筹学:动态规划

    预习准备 (一)实验目的:安装WinQSB软件,了解WinQSB软件在Windows环境下的文件管理操作,熟悉软件界面内容,掌握操作命令。用WinQSB软件求解线性规划。 (二)内容和要求:安装与启动软件,建立新问题,输入模型,求解模型,结果的简单分析。 (三)操作步骤: 1.将Wi

    2024年02月04日
    浏览(67)
  • 运筹学—线性规划单纯形表

    什么是标准型数学模型? a. 具有等式约束方程组:一般引入松弛变量将不等式约束转化为等式约束 b. 约束方程右边常数非负:若右边为负,则两边同称-1使其变为非负 c. 所有变量非负 d. 目标函数为max型,对于min型,化为max型 例如:3a+9b=540添加松弛变量c,使得不等式变为3

    2023年04月08日
    浏览(40)
  • 【运筹学】第4讲 线性代数基础

    笔记来源: b站 王树尧SJTU 本节主要对线性代数整体的研究思路(矩阵、行列式的引出)进行梳理,基础计算方法等请自行复习线性代数; 1、目的:解线性方程(未知数次数为1的方程) 2、n元方程组的推广过程 3、n元方程组研究步骤 有没有解? 怎么解? 解是什么? 对于一

    2024年01月23日
    浏览(42)
  • 运筹学的松弛变量和影子价格或者对偶价格

    1、影子价格就是对偶价格,反应的是对偶问题的决策变量的值;对偶问题中,决策变量对应的是原问题的资源,而松弛变量反应的是资源的利用问题,如果某种资源的松弛变量为0,说明这个资源在此模型下面全部用完,入股松弛变量不为0,说明,此资源还有剩余。 2、如果

    2024年02月11日
    浏览(42)
  • 一些关于运筹学和机器学习之间协同作用的思考

    几十年来,运筹学(OR)和机器学习(ML)一直作为两个相对独立的研究领域不断发展。数据科学和人工智能领域的专家可能更熟悉机器学习而不是运筹学,尽管每个机器学习实践者都应该至少了解一些优化技术,因为每个机器学习问题本质上都是一个优化问题。在本文中,我

    2024年02月05日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包