The shortest path
In life, we often face the problem of optimal choice of path, which may be the shortest distance or the shortest time. The shortest path is similar to the choice of shortest distance.
For example, in Shanghai, taking the subway to get somewhere, there are so many subway lines in Shanghai that it looks like a network from the map. There are multiple routes to get somewhere, and we tend to take the shortest one. Of course, in real life, there are also factors such as time and transfer, but this is just an example of what a shortest path is.
Subway transfers seem to be the best route at a glance. However, in some complicated situations, it is difficult for human eyes to determine the optimal route, such as delivering food or driving a car. It is difficult for human eyes to make the optimal choice, because road conditions and other factors, there is no way to judge. That’s where the algorithm comes in to choose the best route. This is also the subject of this article: The Dijkstra algorithm.
Dijkstra algorithm
The Dijkstra algorithm was proposed by Dutch computer scientist Ezekiel Dijkstra in 1956. Breadth first search is used to solve the single source shortest path problem of weighted directed graphs. A shortest path tree is generated by using one vertex as the source node and finding shortest paths from that vertex to all other nodes in the graph.
Dijkstra algorithm steps
1. Mark the selected initial vertices with the current distance being 0 and the remaining vertices set to infinity. 2. Set the non-accessible vertex with the minimum current distance to the current vertex C. 3. For each neighbor vertex N of the current vertex C: add the current distance C to the weight of the edge connecting C — N. If it is less than the current distance of vertex N, it is set to the new current distance of N. 4. Mark the current vertex C as accessed. 5. If there are any non-accessed vertices, repeat Step 2 until all vertices are accessed.
Dijkstra algorithm time complexity
Let’s say we have V for the number of vertices in the graph, E for the number of edges in the graph.
If you use a linked list or array to store the set of all vertices, the running time required to find the shortest path algorithm is
If adjacency list + binary heap is used as priority queue to find the smallest vertex, then the algorithm takes time is
If adjacency list + Fibonacci heap can slightly improve the performance, so that the algorithm running time is achieved
Example of dijkstra algorithm
Dijkstra’s algorithm is used to calculate the shortest path between one vertex (the starting point) and every other vertex in the graph.
Finally, the shortest distances are C — A=1, C — B=4, C — D=2, and C — E=5. The shortest paths are C-A, C-a-b, C-D, and C-A-b – E.
conclusion
Dijkstra algorithm uses breadth-first search to solve the single source shortest path problem of weighted directed graphs. Take one vertex as the source node and find the shortest path from that vertex to all the other vertices in the graph.
When a linked list or array is used as the stored data structure, the time complexity is
However, the efficiency of binary heap or Fibonacci heap can be improved by optimizing the storage structure.
PS: Clear mountains and clear waters begin with dust, knowledge is more valuable than diligence. I got wine. You got a story? Wechat official account: “Clean the dust chat”. Welcome to chat and talk about code.
