代码之家 › 专栏 › 技术社区 › 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 .

推荐文章

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

1 年前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

1 年前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

1 年前

Matvey Androsyuk · 如何使用React在树结构中呈现我的组件,就像IDE中的默认文件结构一样

1 年前

Pengcheng · 这个简单的递归函数的输出是什么?你能详细解释一下吗?

1 年前

b39b332d · 使用C++标准库实现高效间隔存储

2 年前

Paul C · 在维基百科上,将二叉搜索树转换为排序链表的算法是否存在错误?

2 年前

ABGR · 二叉树的直径——当最长路径不通过根时的失败案例

2 年前

SHUBHAM KUMAR · 这两个是否完全相同-->“下限(股份有限公司rbegin(),股份有限公司rend(),i,更大<int>())”和“下限(dec.begin(

2 年前

EpicAshman · 数独棋盘程序中同一列和同一行出现两次的数字

2 年前