多段图最短路径问题 java_动态规划作业-多段图的最短路径问题

一时失言乱红尘 2022-11-03 01:42 40阅读 0赞

多段图的最短路径问题

问题：设图G=(V,E)是一个带权有向图，如果把顶点集合V划分成k个互不相交的子集Vi(2<=k<=n,1<=i<=k),

使得E中的任何一条边，必有u∈Vi, v∈Vi+m(1<=i

t∈Vk为终点。

多段图的最短路径问题为从源点到终点的最小代价路径。

![11709da35245b5ce98945857f0df7c5c.png][]

子问题：设Cuv表示多段图的有向边上的权值，将从源点s到终点t的最短路径长度即为d(s,t),

考虑原问题的部分解d(s,v)，显然有下式成立

d(s,v)=Csu   (∈E)

d(s,v)=min(d(s,u)+Cuv)            (∈E)

算法：多段图的最短路径问题

输入：多段图的代价矩阵

输出：最短长度及路径c\[n\]\[n\]

1.循环变量j从1~n-1重复下述操作，执行填表工作

1.1考察顶点j的所有入边，对于边*∈E,执行下述操作*

1.1.1cost\[j\]=min\{cost\[i\]+c\[i\]\[j\]\}；

1.1.2path\[j\]=使cost\[i\]+c\[i\]\[j\]最小的i;

1.2 j++;

2.输出最短路径长度cost\[n-1\]；

3.循环变量i=path\[n-1\].循环直到path\[i\]=0,输出最短路径经过的顶点；

3.1 输出path\[i\];

3.2 i=path\[i\]

\#include\#include\#include

\#define Max 0xffff

using namespacestd;//动态规划求最短路径

void dp\_path(int c\[\]\[100\], int \*cost, int \*path) \{intm, n;

cout<< "输入顶点个数和边个数" <

cin>> n >>m;//初始化代价矩阵

for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)

c\[i\]\[j\]=Max;//输入代价矩阵

intu, v, s;for (int i = 0; i < m; i++) \{

cin>> u >> v >>s;//cout<

c\[u\]\[v\] =s;

\}for(int i=0;i

cost\[i\]=Max;

path\[0\] = -1;

cost\[0\] = 0;for (int j = 1; j < n; j++) \{for (int i = j-1; i >=0; i--) \{if (cost\[j\] > cost\[i\] +c\[i\]\[j\]) \{

path\[j\]=i;

cost\[j\]= cost\[i\] +c\[i\]\[j\];

\}

\}

\}

cout<

cout<=0)\{

cout<

i=path\[i\];

\}

\}intmain()

\{int c\[100\]\[100\], cost\[100\], path\[100\];

dp\_path(c, cost, path);

getchar();return 0;

\}

[11709da35245b5ce98945857f0df7c5c.png]: /images/20221024/a4e08136190445b4af28e9aa93b4ffb0.png

发表评论取消回复

表情：

评论列表（有 0 条评论，40人围观）

还没有评论，来说两句吧...

相关阅读

相关图：最短路径算法

为笔试题总是出这个，于是想写下思路首先这个算法能解决从起始点，到各个点的最短路径问题. 但是不能解决权值为负数的情况。并且时间复杂度为O(n^2),并且能用堆进行...

一时失言乱红尘/ 2024年04月17日 05:57/ 0 赞/ 75 阅读

相关图论-最短路径问题

图论-最短路径问题 0、摘要 <table> <thead> <tr> <th>算法名称</th> <th>用途</th> <th

今天药忘吃喽~/ 2024年04月08日 08:40/ 0 赞/ 82 阅读

相关漫画：图的 “多源” 最短路径

![format_png][] ![format_png 1][] ————— 第二天 ————— ![format_png 2][] ![

╰半橙微兮°/ 2023年07月17日 11:17/ 0 赞/ 26 阅读

相关漫画：图的最短路径问题

![format_png][] ![format_png 1][] ————— 第二天 ————— ![format_png 2][] ![

蔚落/ 2023年07月17日 09:59/ 0 赞/ 11 阅读

相关无权图单源最短路径问题

一概述无权图：即表示图中的边是没有权重的，或者是所有的边权重为同一个正数。单源：以一个顶点为初始顶点出发，求解该顶点到其他顶点的最短路径。最短路径：定义从顶点

墨蓝/ 2022年12月25日 06:00/ 0 赞/ 216 阅读

相关【最短路径问题（Shortest Path）——图】

最短路径问题（Shortest Path）一、最短路径（Shortest Path）二、迪杰斯特拉（Dijkstra)算法 1、Dijk

Myth丶恋晨/ 2022年12月21日 03:07/ 0 赞/ 170 阅读

相关多段图最短路径问题 java_动态规划作业-多段图的最短路径问题

多段图的最短路径问题问题：设图G=(V,E)是一个带权有向图，如果把顶点集合V划分成k个互不相交的子集Vi(2<=k<=n,1<=i<=k), 使得E中的任何一条边，必有

一时失言乱红尘/ 2022年11月03日 01:42/ 0 赞/ 41 阅读

相关最短路径问题（最短路径）

最短路径问题 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Ot

Love The Way You Lie/ 2022年08月01日 14:48/ 0 赞/ 278 阅读

相关城市交通网（动态规划，最短路径，输出最短路径）

【例9.5】城市交通路网时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】下图表示城市之间的交通路网，线段上的数字表示费用，单

分手后的思念是犯贱/ 2022年06月08日 07:00/ 0 赞/ 378 阅读

相关最短路径（图）

Dijkstra算法 Dijkstra算法为求带权图中从一个顶点（此处假设为Vo）到其它各顶点的最短路径，按路径长度递增的次序产生最短路径，假设所有权值非负。储存结构

矫情吗；*/ 2022年06月02日 03:59/ 0 赞/ 222 阅读