shortest path problem

The shortest path problem is a classic algorithm problem in graph theory research, aiming to find the shortest path between two nodes in a graph (composed of nodes and paths). The shortest path problem is one of the classic problems in the field of combinatorial optimization. It is widely used in many fields such as computer science, transportation engineering, communication engineering, systems engineering, operations research, information theory, and control theory. Dijkstra's algorithm is a classic shortest path algorithm.

The specific forms of the algorithm include: (recommended learning: PHP video tutorial)

The shortest path problem of determining the starting point - that is, the problem of finding the shortest path given the starting node.

The shortest path problem of determining 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 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.

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.

Global shortest path problem - find all the shortest paths in the graph.

Dijkstra algorithm

Dijkstra algorithm is a classic shortest path algorithm. Its basic idea is to set a set S to store the vertices that have found the shortest path, and the initial state of S It only contains the source point v. For vi∈V-S, it is assumed that the directed edge from the source point v to vi is the shortest path. In the future, every time a shortest path v, ..., vk is obtained, vk is added to the set S, and the path v, ..., vk, vi is compared with the original hypothesis, and the one with the smaller path length is chosen as the shortest path, and the above is repeated. Process until all vertices in set V are added to set S. This algorithm is used to find the globally optimal shortest path. When the number of network nodes is large and the number of network edges is large, there are shortcomings such as large memory usage and high time complexity. Moreover, Dijkstra's algorithm cannot solve problems with must-pass point constraints well. Shortest path problem.

Ant colony algorithm

Ant colony algorithm was first proposed by Dorigo, Maniezzo and Colorni in 1991. It is derived from the food-seeking behavior of ants. Through research, it has been found that information is transmitted between individual ants through a type of pheromone called pheromones. Ants can sense the intensity of surrounding pheromones during walking and move in the direction with high pheromone concentration. When an ant finds food, it will release pheromones as a mark on the way back to the nest. , after the companion discovers it, they will find food along this road. When multiple ants among the companions have found food but the path lengths are different, because the time required for ants to travel back and forth on the short path is relatively small, more and more ants will walk through it per unit time. On this path, The stronger the pheromone concentration will be, therefore, there will be more and more ants on the path, and an optimal path will be gradually selected.

Classification

can be divided into two sub-problems, namely the single-source shortest path problem and the shortest path problem between all vertex pairs. The former is to find the shortest path from a certain vertex to all other vertices in the graph. The main algorithms include Dixcher's algorithm; the latter is to find the shortest path between each pair of vertices in the graph. The main algorithms are Floyd's algorithm. German algorithm, etc.

For more PHP related technical articles, please visit the PHP Graphic Tutorial column to learn!

The above is the detailed content of shortest path problem. For more information, please follow other related articles on the PHP Chinese website!