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 so-called single-source shortest path problem means that given the graph G=(V, E), we hope to find the shortest path from the given source node S∈V to each node in V. First, we can find the fact that if P is the shortest path from vs to vj in G and vi is a point in P, then the path from vs along P to vi is the shortest path from vs to vi.

shortest path algorithm

Dijkstra algorithm is a typical shortest path routing algorithm, which is used to calculate the shortest path from one node to all other nodes. The main feature is to expand outward from the starting point until the end. Dijkstra algorithm can get the optimal solution of the shortest path, but it is inefficient because there are many traversal nodes. You can use heap optimization.

Dijkstra algorithm is a very representative shortest path algorithm, which is introduced in detail as the basic content in many professional courses, such as data structure, graph theory, operational research and so on.