Article directory
Shortest path algorithm
Single source shortest path algorithm
Single source shortest path:
Given the directed graph (or undirected graph) G=(V,E)G=(V,E)G=(V,E) and the source point V0 ∈ VV 0 \ in vv0 ∈ V, the shortest path (the sum of weights on the path to the minimum) from v0v ∈ 0v0 to the other vertices in GGG is obtained.

A single source shortest path algorithm for weighted graphs

Example: find the shortest path from v6v ﹣ 6v6 to the source vertex v1v ﹣ 1v1
Note: the weights of the edges in the weighted graph must all be non negative, otherwise, a negative value circle will appear
Example: find the shortest path from v5v to V4vIf you walk along the loop {V5 → v4 → v2 → V5} \ {V {5 \ rightarrow V} {4 \ rightarrow V} 2 \ rightarrow V} {V5 → v4 → v2 → V5} many times, the path length from v5v {5v5 to V4v} will become infinitesimal without the shortest path.
So in the following algorithms, only when the weight of the edge is greater than or equal to 0 is considered. 
Algorithm: Dijkstra algorithm
 Let S = {source vertex v0 + vertex v with shortest path determined} S = \ {source vertex v_ + vertex v with shortest path determined \} S = {source vertex v0 + vertex v with shortest path determined}
 For any uncollected vertex v v v, the definition of "Distence[v]Distence[v]Distence[v] is the shortest path length from the source point v0v_0v0 to vvv, but the path only passes through the vertices in the set SSS. And the minimum length of path {v0 → (V I ∈ S) → V} \ {V {0 \ rightarrow (V ∈ I \ in S) \ rightarrow V \} {v0 → (vi ∈ S) → V}, which is not the shortest path length
 Select one of the uncollected vertices with the lowest value of distence [] distence [] into the set SSS
 When the included vertex vvv enters the set SSS, it may affect the distence [] distence [] value of the adjacent vertices of the vertex vvv not included in the set SSS. Therefore, the value of distence [] distence [] may be updated every time the included vertex enters the set SSS

PN code description
void Dijkstra(Source SV) { while(1) { V = Not included in vertex Distence[]Least value person; if(In this way V Nonexistent) { break; } collected[V]=ture;//Include vertex V for(V Each adjacent node of W) { if(collected[W]==false) { if(Distence[V] + edge<V,W>Weights < Distence[W]) { Distence[W] = Distence[V] + edge<V,W>Weights; Path[W] = V;//Array recording the shortest path } } } } }

code implementation
The figure is as follows://Node representation of Graphs typedef struct GNode { int NV;//Vertex number int NE;//Edge number WeightType G[MaxVertexNum][MaxVertexNum];//Two dimensional array of type WeightType and size MaxVertexNum X MaxVertexNum forms adjacency matrix to save edge information //DataType Data[MaxVertexNum]; / / a onedimensional array of DataType and MaxVertexNum size is used to store vertex information. Select as appropriate }GNode, *MGraph;
There are two main ways to realize the "extract the minimum value of distence [] distence [] from pseudo code":

utilize MinHeap
//A single source shortest path algorithm for weighted graphs (with minimal heap) void DijkstraByMinHeap(MGraph G, Vertex SourceV) { MinHeap H = NULL; MinHeapElementType *Distence = NULL,Temp; int *Path = NULL; int V = 0, AdjV = 0; int i = 0; /************ Distence[]It is used to store the distance from each vertex to the source vertex, and Path [] is used to store the Path************/ Distence = (MinHeapElementType *)malloc(sizeof(MinHeapElementType)*(G>NV)); Path = (int *)malloc(sizeof(int)*(G>NV)); /*************************** Initialize distance array********************************/ for (i = 0; i < G>NV; i++) { Distence[i].Distance = INT_MAX;//The distance from all vertices (except the source vertex) to the source vertex is initialized to be positive infinity (replaced with int UU max) Distence[i].Vertex = i  1;//When Distence[].Vertex is negative, vertex i (i =  Vertex  1) has not found the shortest path to the source vertex Path[i] = 1; } Distence[SourceV].Distance = 0;//The distance from the source vertex to the source vertex is initialized to 0 /************************ Building a minimum heap with the Distence array***************************/ H = BuildMinHeap(Distence, G>NV); /********************** Find the shortest path from all vertices to source vertices***********************/ while (1) { //The minimum heap is used to store vertices where the shortest path is not found, so when the minimum heap is empty, the loop exits if (IsMinHeapEmpty(H)) { break; } //Temp stores the shortest path vertex data (path length and which vertex is the shortest path to the source vertex) among all vertices that have not found the shortest path Temp = DeleteMinHeap(H); V = Temp.Vertex  1; Distence[V].Distance = Temp.Distance;//The shortest distance from vertex V to source vertex was found Distence[V].Vertex = V;//Indicates that vertex V has found the shortest distance //All the neighboring vertices of traversing vertex V have not found the shortest path yet for (AdjV = 0; AdjV < G>NV; AdjV++) { if ((G>G[V][AdjV] != 0) && (Distence[AdjV].Vertex < 0)) { //Because the shortest distance from the vertex v to the source vertex is found, the distance from the critical vertex of V to the source vertex may change, check. if (Distence[AdjV].Distance > Distence[V].Distance + G>G[V][AdjV]) { Distence[AdjV].Distance = Distence[V].Distance + G>G[V][AdjV]; Path[AdjV] = V; //Determine the location of node AdjV in the minimum heap storage array and change its distance from the source vertex SourceV for (i = 1; i <= H>Size; i++) { if (H>Element[i].Vertex == (AdjV  1)) { H>Element[i].Distance = Distence[AdjV].Distance; break; } } //Since the previous step makes H  > element [i]. Release smaller, adjust the location of the elements in the minimum heap in a similar way to the insertion of the minimum heap Temp = H>Element[i]; for ( ; H>Element[i / 2].Distance > Temp.Distance; i = i / 2) { H>Element[i] = H>Element[i / 2]; } H>Element[i] = Temp; } } } } //Print shortest path length table printf("Distence[]: \n"); for (i = 0; i < G>NV; i++) { printf("%3d", Distence[i].Distance); } printf("\n"); for (i = 0; i < G>NV; i++) { printf("%3d", Distence[i].Vertex); } //Print shortest path table printf("\nPath[]: \n"); for (i = 0; i < G>NV; i++) { printf("%3d", Path[i]); } //Free space for application DestroyMinHeap(H); free(Distence); free(Path); }

Direct array sorting
//A single source shortest path algorithm for weighted graphs (direct sorting) void DijkstraBySort(MGraph G, Vertex SourceV) { List L = NULL; ListElementType *Distence = NULL, Temp; int *Path = NULL; int V = 0, AdjV = 0; int i = 0; /************ Distence[]It is used to store the distance from each vertex to the source vertex, and Path [] is used to store the Path************/ Distence = (ListElementType *)malloc(sizeof(ListElementType)*(G>NV)); Path = (int *)malloc(sizeof(int)*(G>NV)); /*************************** Initialize distance array********************************/ for (i = 0; i < G>NV; i++) { Distence[i].Distance = INT_MAX;//The distance from all vertices (except the source vertex) to the source vertex is initialized to be positive infinity (replaced with int UU max) Distence[i].Vertex = i  1;//When Distence[].Vertex is negative, vertex i (i =  Vertex  1) has not found the shortest path to the source vertex Path[i] = 1; } Distence[SourceV].Distance = 0;//The distance from the source vertex to the source vertex is initialized to 0 /****************************** Create a linear table*********************************/ L = CreateList(); /******************************** Copy all the elements in the sentence [] to the linear table and sort********************************/ for (i = 0; i < G>NV; i++) { AddList(L, Distence[i]); } ListBubbleSort(L); /********************** Find the shortest path from all vertices to source vertices***********************/ while (1) { if (IsListEmpty(L)) { break; } Temp = DeleteList(L); V = Temp.Vertex  1; Distence[V].Distance = Temp.Distance;//The shortest distance from vertex V to source vertex was found Distence[V].Vertex = V;//Indicates that vertex V has found the shortest distance //All the neighboring vertices of traversing vertex V have not found the shortest path yet for (AdjV = 0; AdjV < G>NV; AdjV++) { if ((G>G[V][AdjV] != 0) && (Distence[AdjV].Vertex < 0)) { //Because the shortest distance from the vertex v to the source vertex is found, the distance from the critical vertex of V to the source vertex may change, check. if (Distence[AdjV].Distance > Distence[V].Distance + G>G[V][AdjV]) { Distence[AdjV].Distance = Distence[V].Distance + G>G[V][AdjV]; Path[AdjV] = V; } } } //Because of the change of the Distence [], the linear table is empty and the vertices in the Distence [], which do not determine the shortest path, are added to the linear table again and sorted. EnListEmpty(L); for (i = 0; i < G>NV; i++) { if (Distence[i].Vertex < 0) { AddList(L, Distence[i]); } } ListBubbleSort(L); } //Print shortest path length table printf("\nDistence[]: \n"); for (i = 0; i < G>NV; i++) { printf("%3d", Distence[i].Distance); } printf("\n"); for (i = 0; i < G>NV; i++) { printf("%3d", Distence[i].Vertex); } //Print shortest path table printf("\nPath[]: \n"); for (i = 0; i < G>NV; i++) { printf("%3d", Path[i]); } //Release space DestroyList(L); free(Distence); free(Path); }

Operation result



A single source shortest path algorithm for powerless graph
The weighted graph can be regarded as the weighted graph with each edge weight of 1, so it can still be solved by Dijkstra algorithm.
In addition, it can be solved by sequence traversal.
Example: find the shortest path length from each vertex to the source vertex v1

PN code description
void Unweighted(Graph G，Vertex S) { InsertQueue(Q,S); while(!IsQueueEmpty(Q)) { V=DeQueue(Q); for(V Every adjacent vertex of W) { if(Distence[W]==1)//If W is visited { Distence[W]=Distence[V]+1; Path[W]=V; InsertQueue(Q,W); } } } }

code implementation
//A single source shortest path algorithm for powerless graph void Unweight(MGraph G, Vertex SourceV) { Queue Q = NULL; Vertex V = 0, AdjV = 0; int *Distence = NULL, *Path = NULL; int i = 0, j = 0; /************ Distence[]It is used to store the distance from each vertex to the source vertex, and Path [] is used to store the Path************/ Distence = (int *)malloc(sizeof(int)*(G>NV)); Path = (int *)malloc(sizeof(int)*(G>NV)); /*************************** Initialize array********************************/ for (i = 0; i < G>NV; i++) { Distence[i] = 1; Path[i] = 1; } //Create queue Q = CreateQueue(); //The distance from the source vertex to the source vertex is 0, and the source vertex is queued Distence[SourceV] = 0; InsertQueue(Q, SourceV); //Find the shortest path length and path from each node to the source node while (!IsQueueEmpty(Q)) { V = DeleteQueue(Q);//Vertex V out of queue //Traverse adjacency vertex AdjV of vertex V, and queue adjacency vertices that have not been visited for (AdjV = 0; AdjV < G>NV; AdjV++) { if (G>G[V][AdjV] != 0 && Distence[AdjV] == 1)//Adjacency vertex of V not visited { Distence[AdjV] = Distence[V] + 1;//Distance from adjacent vertex of V to source vertex = distance from V to source vertex + 1 Path[AdjV] = V;//Adjacency vertex of V in the path from AdjV to source vertex, the last vertex of AdjV is v InsertQueue(Q, AdjV);//V's adjacency vertices are queued } } } //Output two arrays printf("Distence[]=\n"); for (i = 0; i < G>NV; i++) { printf("%d ", Distence[i]); } printf("\nPath[]=\n"); for (i = 0; i < G>NV; i++) { printf("%d ", Path[i]); } //Free space for application DestroyQueue(Q); free(Distence); free(Path); }

Operation result

Multi source shortest path algorithm
The socalled multisource shortest path problem is to find the shortest path between the vertices of a graph.

Multi shortest path algorithm of weighted graph
 Method 1: for n vertices, each vertex is regarded as the source vertex, and Dijstra algorithm is used.
 Method 2: Floyd algorithm

Steps:
 I \ rightarrow \ {v V < v_k, and v \in V\} \rightarrow v_j \}Dk[i][j] = the minimum length of path {vi → {V ∣ V < v k, and V ∈ V} → vj}; D − 1D { 1} D − 1 is the minimum length of figure GGG Adjacency matrix.
 Know Dk − 1D^{k1}Dk − 1, and deduce the steps of DkD^kDk:

I] [J] = DK − 1[i][j]D^k[i][j]=D^{k1}[i][j]Dk[i][j]=Dk − 1[i][j];

Short path composition: Dk[i][j]=Dk − 1[i][k]+Dk − 1[k][j]D^k[i][j]=D^{k1}[i][k]+D^{k1}[k][j]Dk[i][j]=Dk − 1[i][k]+Dk − 1[k][j]
therefore
Dk[i][j]=min{Dk−1[i][j],Dk−1[i][k]+Dk−1[k][j]} D^k[i][j]=min\{ D^{k1}[i][j],D^{k1}[i][k]+D^{k1}[k][j]\} Dk[i][j]=min{Dk−1[i][j],Dk−1[i][k]+Dk−1[k][j]}

 From the rule of the second step, we can deduce from D − 1D^{1}D − 1 step by step to D ∣ V ∣ 1D ^ {V 1} D ∣ V ∣ 1;
 D ∣ V ∣ 1[i][j] d ^ {V 1} [i] [J] d ∣ V ∣  1[i][j] is the shortest path from vertex VIV ∣ IVI to vertex vjv ∣ jvj.

PN code description
void Floyd() { //Initialize array for(i=0;i<N;i++) { for(j=0;j<N;j++) { D[i][j]=G[i][j]; Path[i][j]=1; } } //From D(1) to D(V1) for(k=0;k<N;k++) { for(i=0;i<N;i++) { for(j=0;j<N;j++) { D[i][j]=min{D[i][j],D[i][k]+D[k][j]}; Path[i][j]=k; } } } }

code implementation
//Multi source shortest path algorithm for weighted graph void Floyd(MGraph G) { WeightType **D = NULL, **Path = NULL; int i = 0, j = 0, k = 0; /*************************** Request space for distance array D*********************************/ D = (WeightType**)malloc(sizeof(WeightType*)*(G>NV)); D[0] = (WeightType*)malloc(sizeof(WeightType)*(G>NV*G>NV)); for (i = 1; i < G>NV; i++) { D[i] = &(D[0][i*G>NV]); } /**************************** Request space for Path array Path*******************************/ Path = (WeightType**)malloc(sizeof(WeightType*)*(G>NV)); Path[0] = (WeightType*)malloc(sizeof(WeightType)*(G>NV*G>NV)); for (i = 1; i < G>NV; i++) { Path[i] = &(Path[0][i*G>NV]); } /******************************* Initialize array*********************************/ for (i = 0; i < G>NV; i++) { for (j = 0; j < G>NV; j++) { D[i][j] = G>G[i][j]; Path[i][j] = 1; } } /***************************** Floyd Algorithm*******************************/ for (k = 0; k < G>NV; k++) { for (i = 0; i < G>NV; i++) { for (j = 0; j < G>NV; j++) { //Because of this comparison, when the adjacency matrix of graph G is initialized, there is no Vertex connected by edges, which is represented by positive infinity if (D[i][k] + D[k][j] < D[i][j]) { D[i][j] = D[i][k] + D[k][j]; Path[i][j] = k; } } } } /************************** Print two arrays***************************/ printf("\nD(k):\n"); PrintTwoDimensionalArray(D, G>NV, G>NV); printf("\nPath[]:\n"); PrintTwoDimensionalArray(Path, G>NV, G>NV); /***************************** Freeing 2D array space******************************/ free(D[0]); free(D); free(Path[0]); free(Path); }

Operation result
Where 1073741823 represents positive infinity and no path.


Multisource shortest path algorithm for graph with no right
The weighted graph can be regarded as the weighted graph with each edge weight of 1, so it can still be solved by Freud algorithm.