Graph shortest path

The path from one vertex to another vertex along the edge of the graph is called the shortest path

Graph shortest paths have many important applications.

For example, in the figure above, v0-V8 has 9 points, which can be regarded as different points. Now we need to plan the shortest route from V0 to some other point

A common algorithm for constructing shortest paths is Dijstra algorithm

Second, Dijstra algorithm

Algorithm idea:

  1. Dijstra’s algorithm is similar to prim’s in the previous article. It first builds the adjacency matrix of the graph and then defines a temporary one-dimensional array that stores the shortest path from v0 to each vertex
  2. Initialize a one-dimensional array to v0 to the value of each vertex. Next, we define another array to store the vertices that have already been accessed
  3. Find the shortest unaccessed path in a temporary one-dimensional array
  4. Traverses the vertex that finds the shortest path and the accessible edge of the vertex. If the sum of the shortest path and edge is less than the shortest path stored in the one-dimensional array, the sum is overwritten as the shortest path of the vertex
  5. Loop 3,4 until all vertices have been traversed
  • Construct the adjacency matrix
Int [] graph0 = new int[]{0, 1, 5, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT}; int[] graph1 = new int[]{1, 0, 3, 7, 5, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT}; int[] graph2 = new int[]{5, 3, 0, MAX_WEIGHT, 1, 7, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT}; int[] graph3 = new int[]{MAX_WEIGHT, 7, MAX_WEIGHT, 0, 2, MAX_WEIGHT, 3, MAX_WEIGHT, MAX_WEIGHT}; int[] graph4 = new int[]{MAX_WEIGHT, 5, 1, 2, 0, 3, 6, 9, MAX_WEIGHT}; int[] graph5 = new int[]{MAX_WEIGHT, MAX_WEIGHT, 7, MAX_WEIGHT, 3, 0, MAX_WEIGHT, 5, MAX_WEIGHT}; int[] graph6 = new int[]{MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 3, 6, MAX_WEIGHT, 0, 2, 7}; int[] graph7 = new int[]{MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 9, 5, 2, 0, 4}; int[] graph8 = new int[]{MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 5, 4, 0};Copy the code
  • Algorithm code
/** * Graph shortest path (the shortest distance between two vertices in the graph), Dijkstra algorithm Public void shortestPathDijstra() {public void shortestPathDijstra() {public void shortestPathDijstra() { Int [] paths = new int[vertexSize]; Arraycopy (matrix[0], 0, paths, 0, vertexSize); isVisited[0] = true; for (int i = 1; i < vertexSize; Int min = MAX_WEIGHT; i++) {// find an unaccessed shortest path among existing paths int min = MAX_WEIGHT; int minIndex = -1; for (int j = 1; j < vertexSize; j++) { if (! isVisited[j] && paths[j] < min) { min = paths[j]; minIndex = j; } } if (minIndex == -1) { continue; } isVisited[minIndex] = true; For (int k = 1; for (int k = 1; k < vertexSize; k++) { if (! isVisited[k] && (min + matrix[minIndex][k] < paths[k])) { paths[k] = min + matrix[minIndex][k]; } } } for (int i = 1; i < vertexSize; I ++) {system.out. println(" paths[I]] ") {system.out. println(" paths[I] "); }}Copy the code
  • You get the shortest path from v0 to each point

3. Topology sorting

Topological ordering of a Directed Acyclic Graph (DAG)G is to arrange all vertices in G into a linear sequence, such that any pair of vertices U and V in the Graph, if edge (u,v)∈E(G), u will appear before V in the linear sequence. In general, such linear sequences are called Topological Order sequences, or Topological sequences.

Simply put, a partial order on a set yields a full order on the set. This operation is called topological sorting.

Topologically ordering the following directed graph, vertices can be treated as different tasks. Some tasks can be executed directly, such as V0, V1, v3, and others can be executed only after all the superior tasks are completed. For example, V4 can be executed only after both v0 and V1 are completed

Sorting ideas:

  1. It can be observed that if the vertex entry degree is 0, it can be executed directly
  2. After completing a task, the edge of the output degree is eliminated, i.e. his next node is missing an input degree
  3. It can be executed after the degree of entry with the next node is also 0
  4. Loop 1, 2, and 3 through all the vertices to finish sorting

Sort code:

  • Construct an adjacency list for each vertex

  • Algorithm code
/** ** Define a stack to store the node with an input degree of 0. If the input degree is 0, the node with an input degree can be executed. After execution, the node with an input degree will be reduced by one. Loop until the Stack is empty */ private void topologicaSort() {Stack<Integer> Stack = new Stack<>(); For (int I = 0; i < adjList.length; i++) { if (adjList[i].in == 0) { stack.push(i); } } int count = 0; // loop out the stack output until the stack is empty while (! stack.isEmpty()) { int index = stack.pop(); System.out.println(" vertex: "+ adjList[index].data); count++; for (EdgeNode edgeNode = adjList[index].firstEdge; edgeNode ! = null; EdgeNode = edgenode.next) {if (--adjList[edgenode.adjvert]. In == 0) {// If (--adjList[edgenode.adjvert]. Stack. Push (edgenode.adjvert); } } } if (count ! = numVertexes) {system.out.println (" Topological sorting failed ！！！！" ); }}Copy the code

The source address