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

问题描述

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

什么是多段图?

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

相关文章

来自专栏数据结构与算法

5935 小球

5935 小球 时间限制: 2 s 空间限制: 16000 KB 题目等级 : 黄金 Gold 题目描述 Description 许多的小球一个一...

2954
来自专栏Petrichor的专栏

leetcode: 78. Subsets

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

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

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

2225
来自专栏Android机动车

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

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

1245
来自专栏mathor

树形DP

 假设现在有一棵树,我只要求出每个结点作为头节点对应子树的最大值和最小值,那么最终答案一定在其中,因此每个结点都有两个信息,最大值和最小值,我把这个信息封装为一...

1444
来自专栏desperate633

LintCode 恢复IP地址题目分析

[ "255.255.11.135", "255.255.111.35" ] (顺序无关紧要)

921
来自专栏向治洪

红黑树深入剖析及Java实现

概述 红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。它是在1972年由Rudol...

2496
来自专栏Golang语言社区

完全二叉树判断,简单而复杂

今天有个人问我如何判断一棵树是完全二叉树。我一下子想不出怎么解决这个问题,按照定义, 严蔚敏那本教材上的说法:一个深度为k,节点个数为 2^k - 1 的二叉树...

3573
来自专栏小樱的经验随笔

平衡树初阶——AVL平衡二叉查找树+三大平衡树(Treap + Splay + SBT)模板【超详解】

平衡树初阶——AVL平衡二叉查找树 一、什么是二叉树 1. 什么是树。 计算机科学里面的树本质是一个树状图。树首先是一个有向无环图,由根节点指向子结点。但是不严...

3334
来自专栏SeanCheney的专栏

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

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

3695

扫码关注云+社区

领取腾讯云代金券