这是旧期中的一个示例问题:
设G =(V,E)是连通的无向图,其中边具有与它们相关联的正整数边权重,并且顶点s∈V是源 . 提供一种算法,对于每个顶点t∈V报告从s到t的非递减路径上的最小最后边缘权重(如果没有这样的路径,则为∞) . 路径v1,v2 ,. . . 如果对于i = 1,2,...... r-2,w(v_i,v_i 1)≤w(v_i 1,v_i 2),则vr不递减 .
我是否正确地认为问题要求我想出一个算法给出带有起始顶点的图形,可以找到最短路径的长度,沿着路径走向时,边缘权重也会增加到其他所有路径顶点它可以达到?
1 回答
该问题要求编写一种算法,该算法提供从源顶点
s
到(可以是任意)顶点的路径t
,其中s
和t
之间的路径权重增加(或保持不变) . 然后它要求获得所有这些可能路径的最后边缘的最小权重 .换句话说,您需要查看从
s
到t
(在权重中应该不减少)的路径在最后一个边缘中给出最低权重 .