Classic Dijkstra and the longest way

Preface

There is a problem to find the shortest path And the question of the longest way , Because the foundation is not solid enough , Naively thought that the relaxation operation should be changed 、 Overload it Priority queue that will do . in fact , classic Dijkstra You can't find the longest way .

classic Dijkstra The longest path principle cannot be found

In the classic Dijkstra in , According to greedy thought , We use one point at a time that is the shortest from the source A To relax other points , And it ensures that this operation will only be carried out once at each point , That is, each point has and only once as a point A（ Except for the farthest point , Because the last point is relaxed, the whole algorithm is over ）.

as everyone knows , Dijastra's use condition is that there is no negative edge in the graph . This is because in a graph where there is no negative edge weight , The shortest path has substructures , The shortest sub path can ensure the shortest total path . According to this nature , There is also a conclusion , The point mentioned above to relax other points A, The distance from the source point is already the shortest （ This is also Dijsktra The premise that each point is only used to relax once ）. However , There is no substructure in the following two cases ：

• There is a negative edge weight , for example

• Seeking the longest way , for example

In a graph where there is no substructure , A point used to relax other points , It may not be the optimal solution . therefore , We can use algorithms that allow multiple relaxation （SPFA、 classic Dijsktra Change to allow one point to relax other points multiple times , In fact, it should be called SPFA 了 ） To find the longest way .

summary

1. Finding the longest path in a positive weighted edge graph can be used SPFA
2. classic Dijsktra You can run the longest way in the full negative weight edge graph 、 Running the shortest path in a full positive weighted edge graph
3. Dijsktra+ The time complexity of heap optimization is O(ElogV)、SPFA(Bellman Ford)+ The time complexity of heap optimization is O(VE).