“This is the 16th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Graph traversal algorithm (depth first traversal, breadth first traversal) we have talked about in the previous article, today let’s look at the shortest path algorithm. Most of the commonly used algorithms for daily work and study have been updated to the algorithm column. Welcome to pay attention to my algorithm column.

What is the shortest path problem?

How do I find the shortest path from vertex A to vertex G in A graph?

Dijkstra and Freude algorithms are commonly used to solve shortest path problems. Of course, for the powerless graph, we can also get the shortest distance through breadth-first traversal. When the target vertex first appears from the layer, the shortest distance is what.

Dijkstra algorithm

Dijkstra algorithm is a famous single source shortest path algorithm. We can obtain the distance table between the starting point and other vertices by dijkstra algorithm.

A single source means a fixed starting point.

Time complexity (O(n²)), which can be reduced to (O(Elogn)) by minimum heap optimization instead of comparing sizes every time.

Dijeste algorithm steps:

  • Create distance table key is corresponding to other vertices, Value is the minimum known distance from the starting point A to the corresponding vertex (default initialized to Max);
  • Iterate over starting point A and find adjacent vertices B and C of starting point A. Get the distance from A to B, the distance from A to C, and refresh the information into the distance table;
  • Find the shortest distance from A in the distance table, which is the vertex C;
  • Traverse vertex C to find adjacent vertices D and F of vertex C (regardless of traversal points). Get the distance from C to D, and then get the shortest distance from A to D; Get the distance from C to F, and thus get the shortest distance from A to F. Refresh this information into the distance table:
  • Repeat until A’s route to all points has been traversed, flushing the shortest distance to the table
package com.zhj.interview; import java.util.*; public class TestDijkstra { public static void main(String[] args) { Graph graph = new Graph(7); initGraph(graph); Map<Integer, Integer> distanceMap = dijkstra(graph, 0); System.out.println(distanceMap.get(6)); } public static Map<Integer, Integer> Dijkstra (Graph Graph, int startIndex) {// initialize Map<Integer, Integer> distanceMap = new HashMap<>(); Set<Integer> accessedSet = new HashSet<>(); accessedSet.add(startIndex); int size = graph.vertices.length; for (int i = 0; i < size; i++) { if (i ! = startIndex) { distanceMap.put(i, Integer.MAX_VALUE); } } for (Edge edge : graph.adj[startIndex]) { distanceMap.put(edge.index, edge.weight); } for (int i = 0; i < size; i++) { if (i ! = startIndex) {// minDistanceFromStart = integer.max_value; int minDistanceIndex = -1; for (int j = 0; j < size; j++) { if (j ! = startIndex && ! accessedSet.contains(j) && distanceMap.get(j) < minDistanceFromStart) { minDistanceFromStart = distanceMap.get(j); minDistanceIndex = j; } } if (minDistanceIndex == -1) { break; } accessedSet.add(minDistanceIndex); for (Edge edge : graph.adj[minDistanceIndex]) { if (accessedSet.contains(edge.index)) { continue; } int weigth = edge.weight; int preDistance = distanceMap.get(edge.index); if (weigth ! = Integer.MAX_VALUE && (minDistanceFromStart + weigth) < preDistance) { distanceMap.put(edge.index, minDistanceFromStart + weigth); } } } } return distanceMap; } /* * private static class Vertex {String data; Vertex(String data) { this.data = data; }} /* * Edge */ private static class Edge {int index; int weight; Edge(int index, int weight) { this.index = index; this.weight = weight; }} private static Graph {private vertices []; private LinkedList<Edge> adj[]; Graph(int size) { vertices = new Vertex[size]; adj = new LinkedList[size]; for (int i = 0; i < adj.length; i++) { adj[i] = new LinkedList<>(); / / private static void initGraph(Graph Graph) {Graph. Vertices [0] = new Vertex("A"); / / private static void initGraph(Graph Graph) {Graph. Vertices [0] = new Vertex("A"); graph.vertices[1] = new Vertex("B"); graph.vertices[2] = new Vertex("C"); graph.vertices[3] = new Vertex("D"); graph.vertices[4] = new Vertex("E"); graph.vertices[5] = new Vertex("F"); graph.vertices[6] = new Vertex("G"); Graph. Adj [0]. Add (new Edge (1, 7)); Graph. Adj [0]. Add (new Edge (2, 6)); Graph. Adj [1]. The add (new Edge (0, 7)); Graph. Adj [1]. The add (new Edge (3, 3)); Graph. Adj [1]. The add (new Edge (5, 4)); Graph. Adj [2]. The add (new Edge (0, 6)); Graph. Adj [2]. The add (new Edge (3, 1)); Graph. Adj [2]. The add (new Edge (4, 4)); Graph. Adj [3]. The add (new Edge (1, 3)); Graph. Adj [3]. The add (new Edge (2, 1)); Graph. Adj [3]. The add (new Edge (4, 5)); Graph. Adj [3]. The add (new Edge (5, 1)); Graph. Adj [4]. The add (new Edge (2, 4)); Graph. Adj [4]. The add (new Edge (3, 5)); Graph. Adj [4]. The add (new Edge (6, 2)); Graph. Adj [5]. The add (new Edge (1, 4)); Graph. Adj [5]. The add (new Edge (3, 1)); Graph. Adj [5]. The add (new Edge (6, 6)); Graph. Adj [6]. The add (new Edge (4, 2)); Graph. Adj [6]. The add (new Edge (5, 6)); }}Copy the code

Floyd algorithm (Floyd)

What if they were to say, what’s the shortest distance between all the vertices in the graph? Although the dijkstra algorithm can also be used to solve this problem, the time complexity of the Dijkstra algorithm itself is too high, and the time complexity of the dijkstra algorithm is O(n³) for each point.

This is where The Freudian algorithm comes in, which is an algorithm for finding the shortest path between multiple sources in a weighted graph.

The core of Freude algorithm is to derive the shortest distance of all vertices step by step by using the relay vertices between two points.

Freudian algorithm steps:

  • Create a collar matrix with weights

    In the adjacency matrix, each number represents the direct distance from one vertex to another, which does not involve any relay vertices.

  • If we assume that only vertex A is allowed as A relay vertex, what does the distance between vertices look like?

    The distance between B and C was originally infinite. Now, with A as the relay, the distance is shortened to AB distance +AC distance =7+6=13, and the corresponding matrix elements are updated

  • Then, if we use vertex A and B as relay vertices, what will the distance between the vertices look like?

    The distance between A and D was originally infinite, and then B was used as the relay, and the distance was shortened to AB +BD =7+3=10. The distance between A and F was originally infinite. Now B was used as the relay, and the distance was shortened to AB +BF =7+4=11.

  • Then, A, B, C, and so on, all points can be relay points (minimum if repeated).

  • And then you get the shortest distance from point to point

Code implementation:

package com.zhj.interview; public class TestFloyd { public static void main(String[] args) { int[][] matrix = { {0,7,6, Integer. MAX_VALUE, Integer. MAX_VALUE, Integer. MAX_VALUE, Integer. MAX_VALUE}, {7, 0, Integer. MAX_VALUE, 3, Integer. MAX_VALUE, 4, Integer. MAX_VALUE}, {6, Integer. MAX_VALUE, 0,1,4, Integer. MAX_VALUE, Integer. MAX_VALUE}, {Integer. MAX_VALUE, 3,1,0,5,1, Integer. MAX_VALUE}, {Integer. MAX_VALUE, Integer. MAX_VALUE, 4,5,0, Integer. MAX_VALUE, 2}, {Integer. MAX_VALUE, 4, Integer. MAX_VALUE, 1, Integer. MAX_VALUE, 0, 6}, {Integer. MAX_VALUE, Integer. MAX_VALUE, Integer. MAX_VALUE, Integer. MAX_VALUE, 2,6,0}}; floyd(matrix); } public static void floyd(int[][] matrix) { for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix.length; j++) { for (int k = 0; k < matrix.length; k++) { if (matrix[j][i] == Integer.MAX_VALUE || matrix[i][k] == Integer.MAX_VALUE) { continue; } matrix[j][k] = Math.min(matrix[j][k],matrix[j][i] + matrix[i][k]); }} system.out.println (" shortest path matrix: "); for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[i].length; j++) { System.out.print(matrix[i][j] + "\t"); } System.out.println(); }}}Copy the code