代码之家 › 专栏 › 技术社区 › user8303828

如何使用Dijkstra找到更多路线?

dijkstra graph-algorithm algorithm

user8303828 · 技术社区 · 8 年前

我实现了Dijkstra算法来寻找两点之间的最短路径。如何修改它以查找N条最短路径?我的想法是给之前找到的路径的最后一个节点添加一个小权重,但它并不总是正常工作。有什么想法吗?

1 回复 | 直到 8 年前

FrankS101 8 年前

您试图解决的问题称为 K shortest path problem . 解决这个问题的第一个算法是1971年由 Yen ,使用任何最短路径算法寻找最佳路径,然后继续寻找最佳路径的K 1偏差。

算法的运行时间复杂度为 O(kn(m + n log n)) ,这是伪多项式,其中 m 表示边和边的数量 n 是顶点数。

可以在几种编程语言中找到该算法的实现 here .

推荐文章

Sergio · 如何限制neo4j图形查询中的打印关系?

8 年前

TimothyW553 · 为什么我不能(for)循环图形节点和边的输入?

8 年前

user8303828 · 如何使用Dijkstra找到更多路线?

8 年前

flowero · Dijkstra第一个访问的节点

8 年前

user1746460 · 基于路径权重和节点财产dijkstra的遍历

11 年前

Jefferson X Masonic · 用Python查找英文维基百科中两篇文章之间的最短路径

13 年前

Alessandroempire · 用散列码在Java中实现Dijkstra算法

13 年前

alvonellos · 将dijkstras转换为*python

13 年前

Gnosophilon · boost::dijkstra_shortest_path是否覆盖内部图权重?

13 年前