The algorithm used to solve the shortest path problem is called "shortest path algorithm", sometimes referred to as "path algorithm" for short. The most commonly used path algorithms are Dijkstra algorithm, A* algorithm, SPFA algorithm, Bellman-Ford algorithm and Floyd-Warshall algorithm. This paper mainly introduces three of them. The shortest path problem is a classical 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 form of the algorithm includes: the problem of determining the shortest path of the starting point, that is, the problem of finding the shortest path by the nodes with known starting points. 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 by knowing the end point node. In undirected graph, this problem is completely equivalent to the problem of determining the starting point, while in directed graph, this problem is equivalent to the problem of determining the starting point by reversing all paths. The problem of determining the shortest path between the starting point and the end point: that is, knowing the starting point and the end point, finding the shortest path between two nodes. Global shortest path problem: find all the shortest paths in the graph. Floyd finds the shortest path of multi-source non-negative weight edge. Record the chart with a matrix. The timeliness is poor and the time complexity is O (V 3). 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: let di, j, k be the length of the shortest path from I to j with only (1) middle nodes, and set it as intermediate nodes. 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, we can directly iterate on the original space, so that the space can be reduced to two dimensions. The Floyd-Warshall algorithm is described as follows: 1. For k ← 1 to ndo2. For i ← 1 to ndo3. For j ← 1 to ndo4. If (di, k+dk, j < Di, j) then 5. Di，j ← Di，k + Dk，j； Where di and j represent the cost from point I to point J. When di and j are ∞, there is no connection between the two points. Dijkstra finds the shortest path without negative weight for a single source. Good timeliness and time complexity of O(V*V+E). o(V * lgV+E * lgV)= & gt； O(E*lgV). in the case of sparse graph, E=V*V/lgV, so the time complexity of the algorithm can be o (v 2). If Fibonacci heap is a priority queue, then the time complexity of the algorithm is O(V*lgV+E). Bellman-Ford finds the shortest path of a single source and can judge whether there is a negative weight ring (if there is, there is no shortest path), which has good timeliness and time complexity of O(VE). Berman-Ford algorithm is an algorithm to solve the single-source shortest path problem. The shortest path problem of single source point refers to: given a weighted directed graph G and source point S, for any point V in graph G, find the shortest path from S to V. Different from Dijkstra algorithm, in Bellman-Ford algorithm, the weight of edges can be negative. Suppose we can find a loop 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 loop is negative. Then through this loop, the shortest path of any two points in the loop can be infinitely small. If this negative loop is ignored, the program will run forever. Berman-Ford algorithm has the ability to distinguish this negative cycle. SPFA is Behrman-Ford's queue optimization, which has relatively good timeliness and time complexity o (ke) (k