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:

  1. Beg from verticesaThe single source shortest path to start with is the distance to each point in the graphaOf the shortest circuit.

  1. The selecteda, the tag has been visited, first initialize each point in the graph andaIn 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.cDirectly with theaConnect, at this pointdist[b]=8.dist[c]=4. The other pointdist[i]=NaN,The rest of the operation is just updating thisdistThe array.

  1. To choosedistMinimal element extension, obviouslyc, the tagvisitAt this time throughcPoints,f.eAlso produces a new andaThe distance is updated at this timedistArray, their previous distance from A is zeroNaNOf course, as long as the original withaThe distance is greater than throughcwithaDistance, all need to be updated.

  1. To find out thevisitIn thedistThe smallest point, find itfBecause theb, d, eWith thefAdjacent, that’s when the comparison passesfAnd afteraIf the distance is greater than the originaldistShort, updatedist.

  1. Select the verticesb.

  1. Select vertexd, eForm the shortest path.

DijkstraAlgorithm 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