This is the 10th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Shortest path Weighted path length: A path from a vertex v0 to any vertex vi in the graph (there may be multiple choices to reach vi) is the sum of the weights of the edges, where the shortest weighted path length is called the shortest path

1. Find the single source shortest path using Dijkstra. Let’s look at an example to introduce Dijkstra

(Photo from online)

We choose the shortest path from 1 to 2,3,4,5,6

  1. 1->2 possible paths are :(1,2) =1

  2. From 1 to 3,4,5,6, and 2 is added for assistance. At present, the shortest path can be determined as (1,2)+(2,4)=4. Other paths are relatively large.

  3. (1,2)+(2,4)+(4,3)=8. Other paths to 3 are larger than 8. 1->3 choose (1,2)(2,4)(4,3).

  4. The path of 1 to 5, 6, you can now add 2 and 4 assist (1, 2) + (2, 4) + (4, 3) + (3, 5) = 13 other paths to 3 are bigger than 13 path 1 – > 5 selection (1, 2) (2, 4) (4, 3) (3, 5)

  5. Last 1 to 6 (1, 2) + (2, 4) + (4, 3) + (3, 5), (5, 6) = 17 other paths to 3 is larger than 17 path 1 – > 6 choice (1, 2), (2, 4) (4, 3) and (3, 5) (5, 6)

In the process of implementing the above, consider further:

What is the shortest path length from v0 to each vertex stored (in an array) : dist[] represents the shortest path length from v0 to each point. The initial state is the distance from v0 directly to each vertex.

So how do you know the sequence of vertices of the shortest path and you need the path array to record the vertex other than the vertex VI that represents the last edge of the shortest path between source v0 and vertex VI

How do we know which of our nodes are undetermined? S [I]=0 indicates that the shortest path of vertex vi is not determined, and s[I]=1 indicates that the shortest path of vertex vi is determined

Code implementation :(adjacency matrix representation)

Void Dijkstra(Grapha G, int v) {void Dijkstra(Grapha G, int v) { int path[G.vexnum]; int s[G.vexnum]; for(i=0; i<G.vexnum; i++){ dist[i] = G.edge[v][i]; s[i] = 0; If (G.e dge [v] [I] < Max) {/ / Max can be arbitrarily set a maximum path [I] = v; }else { path[i]=-1; }} s[v]=1; // The source point value is initialized directly to 1; path[v]=-1; for(int i=0; i<G.vexnum; I++){// specify the shortest path from v0 to a vertex in one loop int Min = Max; // This is just an initial reference value min can change at any time int u; // for(int j=0; j<G.vexnum; J++) {/ / it a loop in each node of the shortest path from where v0 to find if (s = = 0 [j] && dist [j] < min) {min = dist [j]; u = j; } } s[u]=1; // find the shortest path to a vertex u for(int j=0; j<g.vexnum; J++){// this loop updates dist, Path array because when the shortest path of a vertex is chosen then that vertex can be assisted by v0 vertices there may be shorter paths than directly to vi if(s[j]==0 && Dist [u]+ g.edge [u][j] < dist[j]){dist[j] = dist[u]+G.edge[u][j]; path[j] = u; }}}}Copy the code

Time complexity: O (| V | 2)

But what if the weights are negative? Then, there will be problems in the calculation of this method, so the Floyd algorithm appears, and the Floyd algorithm will be shared later