algorithm - 从一个源经过 N 条边的最短路径

Question

在我的经济学研究中，我目前正在处理一个特定的最短路径问题：

给定一个边上有权重的有向确定性动态图，我需要从一个源 S 中找到最短路径，该路径经过 N 条边。该图可以有循环，边权重可以是负数，并且允许路径多次通过顶点或边。

有没有解决这个问题的有效算法？

标签： algorithmoptimizationgraphshortest-path

Answer 1

一种可能性是：

首先在图中找到最低的边权重。

然后从起始边缘（最初是从起始点的空路径）构建所有路径的优先级队列，其中所有尚未处理的边缘都被视为具有最低权重。

主循环：

1. 从队列中删除权重最低的路径。
2. 如果路径有 N 条边，你就完成了
3. 否则将该路径的所有可能的单边扩展添加到优先级队列

然而，这个简单的算法有一个缺陷——你可能会多次重新访问一个顶点作为 i:th 边（访问第 2 和第 4 是可以的，但是在两个不同的路径中的第 4 是问题），这是低效的。

可以通过在上面的第 3 步中跳过它们来改进算法，因为优先级队列保证到顶点的第一个部分路径对该顶点具有最低的权重和，并且路径的其余部分不取决于您如何到达顶点（因为可以复制边和顶点）。