Among the paths that start from a vertex and reach another vertex along the edges of the graph, the path with the smallest sum of weights on each edge is called the shortest path. There are the following algorithms to solve the shortest path problem, Dijkstra algorithm, Bellman-Ford algorithm, Floyd algorithm and SPFA algorithm, etc.
Definition
The shortest path problem is a classic algorithm problem in graph theory research, aiming to find graph ( The shortest path between two nodes (composed of nodes and paths). The specific form of the algorithm includes:
(1) The problem of determining the shortest path from the starting point - that is, the problem of finding the shortest path when the starting node is known. Suitable for using Dijkstra's algorithm. (Recommended learning:PHP Video Tutorial)
(2) The problem of determining the shortest path to the end point - Contrary to the problem of determining the starting point, this problem is to find the shortest path if the end node is known question. In an undirected graph, this problem is completely equivalent to the problem of determining the starting point. In a directed graph, this problem is equivalent to the problem of determining the starting point by reversing the directions of all paths.
(3) The problem of determining the shortest path between the starting point and the ending point - that is, given the starting point and the ending point, find the shortest path between the two nodes.
(4) Global shortest path problem-find all the shortest paths in the graph. Suitable for using Floyd-Warshall algorithm.
Dijkstra
Find the shortest path with a single source and no negative weight. The timeliness is good, and the time complexity is O(V*V E). If the source point is reachable, O(V*lgV E*lgV) =>O(E*lgV).
When it is a sparse graph, E=V*V/lgV, so the time complexity of the algorithm can be O(V^2). If Fibonacci heap is used as a priority queue, the algorithm time complexity is O(V*lgV E).
Floyd
Find the shortest path with multiple sources and no negative weight edges. 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. It can correctly handle the shortest path problem of directed graph or negative weight.
Bellman-Ford
To find the shortest path from a single source, you can determine whether there is a negative weight loop (if there is, then there is no shortest path),
Timeliness Better, time complexity O(VE).
The Bellman-Ford algorithm is an algorithm for solving the single-source shortest path problem.
SPFA
is Bellman-Ford's queue optimization, which has relatively good timeliness and a time complexity of O(kE). (k<
Similar to the Bellman-ford algorithm, the SPFA algorithm uses a series of relaxation operations to obtain the shortest path from a certain node to all other nodes in the graph. The difference is that the SPFA algorithm maintains a queue so that after the current shortest path of a node is updated, there is no need to immediately update other nodes, thus greatly reducing the number of repeated operations.
For more PHP-related technical articles, please visit thePHP Graphic Tutorialcolumn to learn!
The above is the detailed content of shortest path algorithm. For more information, please follow other related articles on the PHP Chinese website!