In many routing problems, finding the shortest path or least weighted path from one vertex to another vertex in a graph is a very important refining process. Formally stated, given a weighted directed graph G = (V, E), the shortest path from vertex S to vertex T in V is the path with the least cost to connect S to t in edge set E. To do this, we must first solve the more general single-source shortest path problem. In the single source shortest path problem, the shortest path force from one initial vertex S to other adjacent vertices is calculated.
Dijkstra algorithm
Dijkstra algorithm is one of the solutions to single source shortest path problem. Dijkstra generates a shortest path tree with a root as the starting vertex S and branches as the shortest paths from vertex S to all other vertices in graph G. This algorithm requires all ownership values in the graph to be non-negative. Like Prim, Dijkstra uses greedy algorithms that always add the shortest edge that currently looks closest to the shortest path.
Basically, Dijkstra’s algorithm finds the current closest point by selecting a vertex and continuously probing the edges associated with it, similar to breadth-first search.
Algorithm flow:
- Beg from vertices
a
The single source shortest path to start with is the distance to each point in the grapha
Of the shortest circuit.
- The selected
a
, the tag has been visited, first initialize each point in the graph anda
In real code, we usually use an arraydist[i]
Store this value, and if temporarily unreachable, store a maximum value in it. As shown in the figure, onlyb
.c
Directly with thea
Connect, at this pointdist[b]=8
.dist[c]=4
. The other pointdist[i]=NaN,
The rest of the operation is just updating thisdist
The array.
- To choose
dist
Minimal element extension, obviouslyc
, the tagvisit
At this time throughc
Points,f
.e
Also produces a new anda
The distance is updated at this timedist
Array, their previous distance from A is zeroNaN
Of course, as long as the original witha
The distance is greater than throughc
witha
Distance, all need to be updated.
- To find out the
visit
In thedist
The smallest point, find itf
Because theb, d, e
With thef
Adjacent, that’s when the comparison passesf
And aftera
If the distance is greater than the originaldist
Short, updatedist
.
- Select the vertices
b
.
- Select vertex
d, e
Form the shortest path.
Dijkstra
Algorithm implementation:
1 function Dijkstra(Graph, source):
2
3 create vertex set Q
4
5 for each vertex v in Graph: // Initialization
6 dist[v] ← INFINITY // Unknown distance from sourceTo v 7 prev[v] ← UNDEFINED // Previous nodein optimal path from source
8 add v to Q // All nodes initially in Q (unvisited nodes)
9
10 dist[source// Distance, Distance, Distance, Distancesource to source11 to 12while Q is not empty:
13 u ← vertex in Q with min dist[u] // Source node will be selected first
14 remove u from Q
15
16 for each neighbor v of u: // where v is still inQ. 17 Alt ← Dist [U] + Length (u, V) 18ifAlt < dist[v]: // A shorter path to V has been found 19 dist[V] ← Alt 20 prev[v] ← U 21 22return dist[], prev[]
Copy the code