The shortest path

Non-net graph: it has no edge weight, the so-called shortest path, in fact, refers to the path between two vertices through the least number of edges; Net graph: a path with the least sum of edge weights between two vertices, and we call the first vertex on the path the source and the last vertex the destination.

Dijkstra algorithm

Typical shortest path algorithm, used to calculate the shortest path from one node to other nodes. The main feature is to start from the center to the outer layer of expansion, until the extension to the end. An algorithm that generates shortest paths in ascending order.

Problem description

In the undirected graph G=(V,E), assuming that the length of each edge E[I] is W [I], find the shortest path from vertex V0 to the remaining points.

Train of thought

  1. Initially, S contains only the source point, that is, S = {v}, and the distance of v is 0. U contains other vertices except v. If v has an edge with the vertex U in U, then < U,v> has a weight; otherwise, < U,v> has a weight of ∞.

  2. Select a vertex k from U with the smallest distance v and add K to S (the selected distance is the shortest path length from v to K).

  3. Take vertex K as the center, modify the distance of each vertex in U; If the distance from source point V to vertex u (through vertex k) is shorter than the original distance (without vertex k), then the distance value of vertex U is modified to = the shortest path from v to k + the path from v to k.

  4. Repeat steps B and C until all vertices are contained in S.

The value of finalPath is used in the code to distinguish between set S and set U

  • FinalPath divides vertices into two types. FinalPath [I] = 0 indicates that the shortest path is not obtained, and finalPath[I] = 1 indicates that the shortest path is obtained.
  • PathSrc [I] stores the precursor vertices of vertex I.
  • ShortPath [I] Stores the shortest path from V0 to vertex I.

implementation

1static int[] pathSrc = new int[9]; 2static int[] shortPath = new int[9]; 3static void shortestPath_DijkStra(MGraph m, Int v0) {4 // finalPath[w] = 1 finalPath[w] = 1 6 for (int i = 0; i < m.numVertexes; i++) { 7 finalPath[i] = 0; 8 shortPath[i] = m.arc[v0][i]; 9 pathSrc[i] = 0; ShortPath [v0] = 0; // shortPath[v0] = 0; FinalPath [v0] = 1; finalPath[v0] = 1; 15 for (int i = 1; i < m.numVertexes; I++) {16 int min = INFINITY; 18 int k = 0; 19 for (int w = 0; w < m.numVertexes; w++) { 20 if(shortPath[w] < min && finalPath[w] == 0) { 21 min = shortPath [w]; 22 k = w; 23 } 24 } 25 finalPath[k] = 1; For (int w = 0; w < m.numVertexes; If (finalPath[w] == 0 && (min + m.rc [k][w]) < shortPath[w]) {29 // If (finalPath[w] == 0 && (min + m.rc [k][w]) < shortPath[w]) {29 // 30 shortPath[w] = min + m.rc [k][w]; // Change the path length 31 pathSrc[w] = k; // Modify the vertex subscript W of the precursor vertex 32} 33} 34} 35}Copy the code

1-14: Initialize the array, add vertex V0 to the array, read the distance between V0 and each vertex to shortPath

15-34: Loop to get the shortest path from V0 to each vertex

16-24: obtains the shortest path in shortPath and marks the vertex subscript as k and the minimum value as min.

25: sets vertex K to have found the shortest path

26-34: If the distance from source point V0 to vertex W (through vertex k) is shorter than the original distance (without vertex k) (V0->Vk +Vk->Vw is less than the path of shortPath), Modify the path of shortPath and the precursor vertices of vertex Vk.

Execute the process

V0->V1:

The current shortPath array for,1,5,65535,65535,65535,65535,65535,65535 {0}. Loop through the shortPath array to get K=1, min=1; From k=1, it indicates that the nearest vertex to V0 is V1. From shortPath[1]=1, we know that the shortest distance between V0 and V1 is 1. Set finalPath[1] corresponding to V1 to 1. The finalPath array is {1,1,0,0,0,0,0,0}.

V1->V2: 

Assuming that the shortest path of V0 and V1 has been found, the edges of V1 and other vertices are calculated to get the current shortest distance between V0 and them. Where V0 originally, because min = 1 (- > V2 = shortPath [2] = 5, now where V0 – > V1 – > V2 = shortPath [2] = min + 3 = 4, where V0 – > V1 – > V3 = shortPath [3] = min + 7 = 8, Where V0 – > V1 – > = shortPath v4 [4] = min + 5 = 6, as a result, the shortPath array current value for,1,4,8,6,65535,65535,65535,65535 {0}. PathSrc [2]=1, pathSrc[3]=1, pathSrc[4]=1, which means that the precursor of the shortest path from V0 to V2, V3, V4 is V1. The pathSrc array value is {0,0,1,1,1,0,0,0,0}.

V2-V3:

ShortPath [4]=6. Now V0→V2→V4=shortPath[4]=min+1=5. Where V0 – V2 – V5 = shortPath [5] = min + 7 = 11, therefore, the current value is: the shortPath array,1,4,8,5,11,65535,65535,65535 {0}. While originally pathSrc[4]=1, now pathSrc[4]=2, pathSrc[5]=2, which indicates that the shortest paths from V0 to V4 and V5 are all preceded by V2. The pathSrc array value is {0,0,1,1,2,2,0,0,0}.

And then the cycle is exactly the same

The results of

  • FinalPath array: [1,1,1,1,1,1,1,1]. It means that all vertices have completed the shortest path search.
  • ShortPath array: [0,1,4,7,5,8,10,12,16] It represents the number of shortest paths from V0 to each vertex. Such as [8] D = 1 + 3 + 1 + 2 + 3 + 2 + 4 = 16.
  • The pathSrc array is: [0,0,1,4,2,4,3,6,7]. For example, P[8]=7, which means the shortest path from V0 to V8, vertex V8’s precursor vertex is V7, and P[7]=6 means V7’s precursor is V6, P[6]=3, indicating V6’s precursor is V3. Similarly, the shortest path from V0 to V8 is V0→V1→V2→V4→V3→V6→V7→V8.

The resulting array pathSrc and shortPath is the shortest path and path length from V0 to any vertex.

For example, D[5]=8 shows that its path length is 8, and P[5]=4 shows that V5’s precursor vertex is V4, so the shortest path from V0 to V5 is V0→V1→V2→V4→V5.

Dijkstra algorithm is used to solve the shortest path problem from a source point to other vertices. The time complexity of the algorithm is 0 (n2).

What if we need to know the shortest path from any vertex like V3 to V5, V1 to V7 to all the other vertices? At this point, the simple way is to run Dijkstra algorithm once for each vertex as the source point, which is equivalent to repeating the loop on the basis of the original algorithm, and the time complexity of the whole algorithm becomes 0(n3).

Floyd algorithm

Solve shortest path problem from all vertices to all vertices

The time complexity from all vertices to all vertices is also 0(n3), but its algorithm is very simple and elegant, which can make people feel the infinite charm of wisdom.

The book can not go down, too difficult, tomorrow should also go to work, free to read again