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

问题描述

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

什么是多段图?

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

相关文章

来自专栏专注研发

选择排序—堆排序(Heap Sort) 没看明白,不解释

时称之为堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)。 若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点的值均不大于(或...

642
来自专栏小文博客

蓝桥杯 C语言省赛 习题3 移动距离

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

线段树入门总结

线段树的入门级 总结       线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。       对于...

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

Q169 Majority Element

Given an array of size n, find the majority element. The majority element is the...

3627
来自专栏机器学习与自然语言处理

04-树4. Root of AVL Tree-平衡查找树AVL树的实现

  对于一棵普通的二叉查找树而言,在进行多次的插入或删除后,容易让树失去平衡,导致树的深度不是O(logN),而接近O(N),这样将大大减少对树的查找效率。一种...

1907
来自专栏python学习路

数据结构与算法(二)

排序与搜索 排序算法(英语:Sorting algorithm)是一种能将一串数据依照特定顺序进行排列的一种算法。 排序算法的稳定性 稳定性:稳定排序算法会让原...

3138
来自专栏Java3y

二叉树就这么简单

一、二叉树就是这么简单 本文撇开一些非常苦涩、难以理解的概念来讲讲二叉树,仅入门观看(或复习)…. 首先,我们来讲讲什么是树: 树是一种非线性的数据结构,相对于...

3888
来自专栏专注研发

哈夫曼树【最优二叉树】【Huffman】

        在很多问题的处理过程中,需要进行大量的条件判断,这些判断结构的设计直接影响着程序的执行效率。例如,编制一个程序,将百分制转换成五个等级输出。大家...

671
来自专栏java一日一条

经典数据结构和算法回顾

最近想回过头来看看以前写的一些代码,可叹为何刚进大学的时候不知道要养成写博客的好习惯。现在好多东西都没有做记录,后面也没再遇到相同的问题,忘的都差不多了。只能勉...

451
来自专栏Python

推导式详解

推导式的套路 除列表推导式和生成器表达式之外,其实还有字典推导式、集合推导式等等。 下面是一个以列表推导式为例的推导式详细格式,同样适用于其他推导式。 vari...

1899

扫码关注云+社区