So I've been working with Dijkstra's algorithm and directed graphs a lot lately. However, I can't seem to figure this out and it's really starting to bother me.
Show how to modify Dijkstra’s algorithm to solve the single source shortest path problem if there is exactly one negative weight edge but no negative weight cycles.
So far my initial thought has been to somehow split up the graphs and perform the algorithm separately, but that's about all I've thought of.
I've actually found an explanation I'm looking for, but I can't seem to follow his explanation
Well answered! I'd like to point out that if the number of negative edges is limited, there are Dijkstra-based algorithms that might do a better job. For example, if there is only one negative edge from u to v, you could run Dijkstra on s and on v, and then take the minimum for each vertex between
d[s]andd[s]+w(u, v)+d[v], giving a complexity of running Dijkstra twice
Remove the negative edge (u, v), run Dijkstra twice: once starting at s (D1) and once starting at v (D2)
The shortest path between s and t is: min(D1[t], D1[u]+D2[t]+w(u, v)).
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments