algorithm - 具有优先节点的最短路径

Question

我必须找到最短路径，我猜 djistra 的算法对此很有效。但是我添加了约束，即节点具有优先级而不是它们之间的距离。所以考虑到优先级我们必须找到最短的路径。任何人都可以对此有所了解。提前致谢。

Answer 1

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

您可以将距离更新为 d_ij_new = d_ij - (pi + pj) .这将确保距离根据所考虑的顶点的优先级而减小。您还需要确保距离不会变为负数。为确保这一点，添加 2 * pmax所有的权重(pi + pj < 2 * pmax)。