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

问题描述

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

什么是多段图?

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

相关文章

来自专栏码匠的流水账

聊聊spring cloud的HystrixAutoConfiguration

本文主要研究一下spring cloud的HystrixAutoConfiguration

992
来自专栏linux驱动个人学习

高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分,其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

9784
来自专栏一个会写诗的程序员的博客

13.12 Spring Boot集成Security中遇到的问题13.12 Spring Boot集成Security中遇到的问题问题1:Spring Boot集成Security使用数据库用户角色

sql语法手误。1?这地方写错了,应该是?1。这在敲代码的时候,手速一旦稍有不慎,就会导致前后顺序颠倒,而导致输入错误。这个虽然说是“低级错误”,但是错误搞起来...

812
来自专栏CodingToDie

Awesome 项目

3475
来自专栏生信技能树

基因名变化太快,比如PAM50

当然准备把这些基因跟ensembl数据库的ID对应的时候我发现少了3个,然后我搜索发现它们的symbol其实被修改了,可以说变化比较快啦,才几年时间,3 of ...

1022
来自专栏IT杂记

Storm客户端提交任务失败原因分析

2560
来自专栏我和未来有约会

silverlight beta 2 将在本周末发布.

太开心了,刚刚收到微软silverlight.net的邮件.  确定了 将在本周末发布beta2. 以下是部分邮件内容 引用: There are some...

1976
来自专栏跟着阿笨一起玩NET

NHibernate分页

转载:http://www.cnblogs.com/tenghoo/archive/2011/02/14/1954393.html

491
来自专栏Ryan Miao

ehcache报错

jfinal2.0+tomcat7+ehcache2.6.11+Linux Linux version 2.6.18-164.el5 (mockbuild@x8...

3729
来自专栏成长道路

org.apache.spark.sql.AnalysisException: Table or view not found: `traintext`.`train`; line 1 pos 14;

恭喜老铁,跟我遇到了一样的问题,接下来是解决方法: 遇到的问题: org.apache.spark.sql.AnalysisException: Table o...

9330

扫码关注云+社区