Shortest Path With Priority Nodes

Question

I have to find shortest path I guess djistra's algorithm is efficient for that. But I have added constraint that nodes have priority other than distance between them. So considering priority we have to find the shortest path. Can anyone spread some light on this. Thanks in advance.

Answer 1

Let's say you have a graph G = (V, E), where V is the set of vertices, E is the set of edges. Since you want to introduce another parameter called priority in a set P, defined as P = {pi | pi is the priority of vertex vi}.

You can update your distance as d_ij_new = d_ij - (pi + pj). This will ensure that the distance decreases as a function of priorities of the vertices being considered. You will also need to make sure the distance does not go negative. To ensure that, add 2 * pmax to all the weights (pi + pj < 2 * pmax).