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

问题描述

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

什么是多段图?

  • 多段图是一个有向、无环、带权 图。
  • 有且仅有一个起始结点(原点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 条评论
登录 后参与评论

相关文章

来自专栏Vamei实验室

纸上谈兵: 树, 二叉树, 二叉搜索树

树的特征和定义 树(Tree)是元素的集合。我们先以比较直观的方式介绍树。下面的数据结构是一个树: ? 树有多个节点(node),用以储存元素。某些节点之间存在...

2087
来自专栏Java爬坑系列

【Java入门提高篇】Day25 史上最详细的HashMap红黑树解析

  当当当当当当当,好久不见,最近又是换工作,又是换房子,忙的不可开交,断更了一小段时间,最重要的一篇迟迟出不来,每次都犹抱琵琶半遮面,想要把它用通俗易懂的方式...

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

剑指OFFER之重建二叉树(九度OJ1385)

题目描述: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7...

2085
来自专栏mathor

Morris遍历

 Morris算法遍历一棵二叉树,时间复杂度O(n),但是空间复杂度却只用神奇的O(1),下面说一下Morris遍历的流程,首先规定来到的当前结点即为cur

671
来自专栏Golang语言社区

解决连通性问题的四种算法

连通性问题 问题概述 先来看一张图: ? 在这个彼此连接和断开的点网络中,我们可以找到一条 p 点到 q 点的路径。在计算机网络中判断两台主机是否连通、在社交网...

5659
来自专栏用户2442861的专栏

红黑树深入浅出

先来看下算法导论对R-B Tree的介绍: 红黑树,一种二叉查找树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条...

802
来自专栏SeanCheney的专栏

《大话数据结构》总结第一章 绪论第二章 算法第三章 线性表第四章 栈和队列第五章 字符串第六章 树第七章 图第八章 查找第九章 排序

第一章 绪论 什么是数据结构? 数据结构的定义:数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 第二章 算法 算法的特性:有穷性、确定性、可行性、输...

3205
来自专栏Bingo的深度学习杂货店

Q907 Sum of Subarray Minimums

Given an array of integers A, find the sum of min(B), where B ranges over every ...

1033
来自专栏Android机动车

数据结构——二叉树的存储结构

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点,并且结点的存储位置,也就是数组的下标,要能体现结点之间的逻辑关系,如双亲与孩子的关系,左右兄弟的关系等。

1005
来自专栏拭心的安卓进阶之路

重温数据结构:树 及 Java 实现

数据结构,指的是数据的存储形式,常见的有线性结构(数组、链表,队列、栈),还有非线性结构(树、图等)。 今天我们来学习下数据结构中的 树。 什么是树 线性结构中...

26410

扫码关注云+社区