代码之家 › 专栏 › 技术社区 › Ka Mal

加权图中最优路径的确定算法

shortest-path graph algorithm

Ka Mal · 技术社区 · 10 年前

这是我的测试练习题,我检查了加权图和一些相关材料,但开始时被卡住了,所以需要一些关于这方面的想法。

假设你想从节点s的家里到你的同伴那里位于a中节点t处的房屋 加权图 G=(V,E,w) 。但是你想去当地的Fishn 如果可以在不增加路径长度的情况下将芯片放置在节点u 超过20%。

(a) 描述一种有效的算法 这将决定一条最佳的s-t路径,如果这样做成本不会太高的话,那么考虑到你在沿途停留u的偏好。(它应该返回从s到t的最短路径或从s到t的包含u的最短路线,具体取决于 )你应该让你的算法尽可能高效地运行

1 回复 | 直到 10 年前

ÐÐ¸ÑÐ°Ð»Ð¸Ð¹ ÐÑÑÐ°Ð¿Ð¾Ð²Ð¸Ñ 10 年前

试试这个 Dijkstra algorithm 。找到从s到t、s到u和u到t的最短路径。然后,借助数学(s到u+u到t>s到t*1.20),您可以看到答案。干杯

推荐文章

Szyszka947 · 我什么时候可以假设Dijkstra算法中的某个顶点已经完成了最短路径

3 年前

Tak · 在Python中获取二维数组中单元格的最短路径

8 年前

The Winter Soldier · 动态最短路径

8 年前

Anathapindika · networkx、moore邻域、最短路径问题

8 年前

Timmathy · 最短路径算法

8 年前

Luca Valentini · 如何在图中找到从s到t到v的所有最小路径的总数?

9 年前

Ka Mal · 加权图中最优路径的确定算法

10 年前

BKS · 两个节点之间所有最短路径列表中的最大值

11 年前

razshan · Edmonds karp算法实际上是如何计算最短路径的?

12 年前

roxrook · 如何用动态规划求解地形图的最短路径?

13 年前