CODEWITHSUNDEEP
algorithmgraph-algorithm
amaldec23
amaldec23

Reputation: 245

Shortest Path With Priority Nodes

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.

Upvotes: 3

Views: 438

Answers (1)

nikhilbalwani
nikhilbalwani

Reputation: 930

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).

enter image description here

Upvotes: 2

Related Questions