算法导论 24-6 双调最短路径 求思路

算法导论 24-6 双调最短路径 求思路
假设有向图G=(V,E),权重函数为w:E->R,并且所有的权重值偶唯一.我们希望找到从源结点s出发的单源最短路径.不过,我们还有一条额外的信息:对于每个结点v in V,从源结点s到结点v的任意最短路径上的边的权重形成一个双调序列.
请给出最有效的算法来解决这个问题,并分析其运行时间.
精确制导1986 1年前 已收到1个回答 举报

吉祥猫猫 幼苗

共回答了14个问题采纳率:92.9% 举报

我也不会,不过算法导论的课后题基本上都有背景文献,如果实在想不出,你试试在google学术里输入bitonic shortest paths,查一查相关的文章都有哪些,最后的算法究竟是什么其实不太重要.

1年前

4
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 16 q. 0.028 s. - webmaster@yulucn.com