动态规划法(五)——多段图问题

问题描述

给定一个多段图,求出多段图中的最短路径和最短路径长度。

什么是多段图?

  • 多段图是一个有向、无环、带权 图。
  • 有且仅有一个起始结点(原点source) 和 一个终止结点(汇点target)。
  • 它有n个阶段,每个阶段由特定的几个结点构成。
  • 每个结点的所有结点都只能指向下一个相邻的阶段,阶段之间不能越界。

数据结构

  • cost数组: 该数组用于记录以某个结点为起点,到终点t的最短路径长度值。 数组的下标表示结点的编号(因此所有结点都必须从0开始依次编号),数组的值表示:以该结点为起点,到终点的最短路径长度。
  • d数组: 该数组用于记录最短路径中出现的所有结点。 下标表示结点的编号,d[i]表示:结点i的后继结点编号。

算法思路

算法流程

  1. 从前往后依次给所有结点编号;序号必须从0开始,依次递增,同一阶段的结点顺序可以随意;
  2. 创建数组cost和d,分别记录每个结点的最短路径长度 和 每个结点最短路径的前驱结点;
  3. 从最后一个结点开始,从后向前,依次计算每个结点的cost值和d值;
  4. 直到将所有结点都计算完毕后,即可得到最短路径。

每个结点cost和d的计算方法

设当前要计算cost[i]的值。

  1. 找到i结点所有的出边,假设出边的终点分别是a、b、c,边上的权值分别是w1、w2、w3;
  2. 分别计算w1+cost[a]、w2+cost[b]、w3+cost[c],将其中最小的那个值作为cost[i];并将最小的那个后继结点作为d[i]。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏python成长之路

列表常用操作

1474
来自专栏java思维导图

正则表达式思维导图,不再难懂

01 一张思维导图 ? 02 导图内容解析 工具 RegexBuddy 语法结构 字符 [ab5@] 匹配"a"或"b"或"5"或"@" [^abc] 匹配a、...

34811
来自专栏算法修养

2016天梯模拟赛 进阶题解

L2-005 集合相似度 题目链接: https://www.patest.cn/contests/gplt/L2-005 题目的意思是要求两个集合的交集中...

3989
来自专栏mwangblog

python字典(Dictionary)

892
来自专栏python学习指南

python字典

本篇将介绍Python里面的字典,更多内容请参考:Python学习指南 Python是什么? Python内置了字典dict的支持,dict全称dicti...

1848
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之合并有序链表(九度OJ1519)

题目描述: 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 (hint: 请务必使用链表。) 输入: 输入可能包含...

1698
来自专栏练小习的专栏

js运算符优先级笔记

运算符的优先级决定了表达式中运算执行的先后顺序,优先级高的运算符最先被执行。 下面是一个简单的例子: 3 + 4 * 5 // 计算结果为23 乘法运算符...

1838
来自专栏流柯技术学院

正则中需要转义的特殊字符

752
来自专栏大闲人柴毛毛

贪心算法(五)——迪杰斯特拉算法

问题描述 给一个有向无环带权图,并给一个起点,求出该原点到所有顶点的最短路径。 ? 数据结构 dis: Map<String,Integer> dis; ...

3489
来自专栏技术之路

c++ 数组

数组就是一组元素的内存位置,各个内存位置可以存储相同数据类型的数据项,而我们可以用相同的变量名引用所有的内存地址 初始化数组 int myA[5]={1,2,3...

1875

扫描关注云+社区