带有优先节点的最短路径

Question

3

我需要寻找最短路径，我猜Dijkstra算法是高效的解决方法。但我添加了一个约束条件，即节点具有除它们之间的距离以外的优先级。因此，我们需要考虑优先级来找到最短路径。请问有人能为此提供一些指引吗？

提前感谢。

- amaldec23

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- nikhilbalwani · Accepted Answer

假设您有一个图形 G = (V, E)，其中 V 是顶点集，E 是边集。由于您想在一个集合 P 中引入另一个名为优先级的参数，定义为 P = {pi | pi 是顶点 vi 的优先级}。

您可以将距离更新为 d_ij_new = d_ij - (pi + pj)。这将确保距离随着考虑的顶点的优先级而降低。您还需要确保距离不会变为负数。为了确保，将 2 * pmax 添加到所有权重中 (pi + pj < 2 * pmax)。