具有优先级节点的最短路径

Question

我必须找到最短的路径，我猜djistra的算法对此有效。但是我增加了约束，即节点之间的距离以外的其他优先级。因此，考虑优先级，我们必须找到最短的路径。任何人都可以对此发表一些看法。预先感谢。

Answer 1

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

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