Definition
The shortest path problem is a classic algorithm problem in graph theory research, which aims to find the shortest path between two nodes in a graph (composed of nodes and paths) . The specific forms of the algorithm include:
(1) The problem of determining the shortest path of the starting point-that is, the problem of finding the shortest path when the starting node is known. It is suitable to use Dijkstra's algorithm.
(2) The problem of determining the shortest path to the end point-contrary to the problem of determining the starting point, this problem is a problem of finding the shortest path when the end node is known. In the undirected graph, this problem is completely equivalent to the problem of determining the starting point. In the directed graph, this problem is equivalent to the problem of determining the starting point in which the directions of all paths are reversed.
(3) The problem of determining the shortest path between the starting point and ending point-that is, knowing the starting point and ending point, find the shortest path between two nodes.
(4) The global shortest path problem-find all the shortest paths in the graph. It is suitable to use the Floyd-Warshall algorithm.
Algorithm
Dijkstra
Find the shortest path with single source and no negative weight. The timeliness is good, and the time complexity is O(V*V+E). If the source is reachable, O(V*lgV+E*lgV)=>O(E*lgV).
In the case of sparse graphs, E=V*V/lgV at this time, so the time complexity of the algorithm can be O(V^2). If the Fibonacci stack is used as a priority queue, the algorithm time complexity is O(V*lgV + E).
Floyd
Find the shortest path with multiple sources and edges without negative weight. Use a matrix to record the graph. The timeliness is poor, and the time complexity is O(V^3).
Floyd-Warshall algorithm (Floyd-Warshall algorithm) is an algorithm to solve the shortest path between any two points, which can correctly handle the shortest path problem of directed graph or negative weight.
The time complexity of Floyd-Warshall algorithm is O(N^3), and the space complexity is O(N^2).
The principle of Floyd-Warshall is dynamic programming:
Suppose Di,j,k are from i to j and only the nodes in the (1..k) set are the intermediate nodes The length of the shortest path.
If the shortest path passes through point k, then Di,j,k = Di,k,k-1 + Dk,j,k-1;
If the shortest path does not pass through point k, then Di,j,k = Di,j,k-1.
Therefore, Di,j,k = min(Di,k,k-1 + Dk,j,k-1, Di,j,k-1).
In the actual algorithm, in order to save space, iterate directly on the original space, so that the space can be reduced to two dimensions.
The description of the Floyd-Warshall algorithm is as follows:
for k ← 1 to n do
for i ← 1 to n do
for j ← 1 to n do
if (Di,k + Dk,j < Di,j) then
Di,j ← Di,k + Dk,j;< /p>
where Di,j represents the cost from point i to point j, when Di,j is ∞, it means that there is no connection between the two points.
Bellman-Ford
To find the shortest path of a single source, you can determine whether there is a negative weight loop (if there is, there is no shortest path),
p>The timeliness is better, and the time complexity is O(VE).
Bellman-Ford algorithm is an algorithm for solving the single source shortest path problem.
The shortest path problem with a single source point refers to:
Given a weighted directed graph G and source point s, for any point v in the graph G, find from s to The shortest path of v.
Different from the Dijkstra algorithm, in the Bellman-Ford algorithm, the edge weight can be a negative number.
Imagine that we can find a cycle from the graph (that is, starting from v and returning to v after several points) and the sum of the weights of all edges in this cycle is negative. Then through this loop, the shortest path between any two points in the loop can be infinitely small. If this negative loop is not dealt with, the program will run forever. The Bellman-Ford algorithm has the ability to distinguish this negative loop.
SPFA
is Bellman-Ford's queue optimization, with relatively good timeliness and time complexity O(kE). (K<
is similar to the Bellman-ford algorithm. The SPFA algorithm uses a series of relaxation operations to obtain the shortest path from a node to all other nodes in the graph. The difference is that the SPFA algorithm maintains a queue, It makes it unnecessary to update other nodes immediately after the current shortest path of a node is updated, thus greatly reducing the number of repeated operations.
SPFA algorithm can be used for graphs with negative edge weights, which is the same as dijkstra The algorithm is different.
Different from the Dijkstra algorithm and the Bellman-ford algorithm, the time efficiency of the SPFA algorithm is unstable, that is, the time required for different graphs is very different.< /p>
In the best case, each node is enqueued only once, then the algorithm actually becomes breadth-first traversal, and its time complexity is only O(E). On the other hand, there are such examples , So that each node is enqueued (V-1) times. At this time, the algorithm degenerates to the Bellman-ford algorithm, and its time complexity is O(VE).
SPFA algorithm is in the negative edge weight graph The above can completely replace the Bellman-ford algorithm, and it also performs well in sparse graphs. However, in a non-negative edge weight graph, in order to avoid the worst case, the more efficient Dijkstra algorithm is usually used, and its use of heap optimization Version. The usual SPFA algorithm does not perform satisfactorily in a type of grid graph.