1. Application Scenario – Shortest path problem
- During the war, there were seven villages (A, B, C, D, E, F, G) in Shengli township. Now there are six postmen who need to deliver mail separately from G point
Six villages A, B, C, D, E and F
-
The distance of each village is represented by A line (weight), for example, A — B is 5 km away
-
Q: How do you calculate the shortest distance from village G to other villages?
-
What is the shortest distance from any other point to any other point?
2. Introduction to Dijkstra algorithm
Dijkstra algorithm is a typical shortest path algorithm used to calculate the shortest path from one node to other nodes. Its main feature is that it spreads out from the starting point (the breadth-first search idea) until it reaches the end point.
3. Dijkstra algorithm process
-
Set the starting vertex to v, the set of vertices v {v1,v2,vi… }, the distance from v to the vertices of v constitutes the distance set Dis, Dis{d1,d2,di… }, the Dis set records the distance from v to each vertex in the graph (to itself can be regarded as 0, the distance from v to vi corresponds to di)
-
Select di with the smallest value from Dis and remove Dis set, and remove the corresponding vertex vi in V set at the same time. In this case, V to vi is the shortest path
-
Update Dis set, the update rule is: compare the distance value from V to the vertex in V set with the distance value from V to the vertex in V set via vi, keep the smaller one (at the same time, the precursor node of the vertex should also be updated as vi, indicating that it is reached through VI)
-
Repeat the two steps until the shortest path vertex is the target vertex
4. Best application of Dijkstra algorithm – shortest path
public class DijkstraAlgorithm {
public static void main(String[] args) {
char[] vertex = {'A'.'B'.'C'.'D'.'E'.'F'.'G'};
// Adjacency matrix
int[][] matrix = new int[vertex.length][vertex.length];
// Indicates that the connection cannot be made
final int N = 65535;
matrix[0] = new int[]{N, 5.7, N, N, N, 2};
matrix[1] = new int[] {5, N, N, 9, N, N, 3};
matrix[2] = new int[] {7, N, N, N, 8, N, N};
matrix[3] = new int[]{N, 9, N, N, N, 4, N};
matrix[4] = new int[]{N, N, 8, N, N, 5.4};
matrix[5] = new int[]{N, N, N, 4.5, N, 6};
matrix[6] = new int[] {2.3, N, N, 4.6, N};
// Create Graph object
Graph graph = new Graph(vertex, matrix);
// Test to see if the graph's adjacency matrix is ok
graph.showGraph();
// Test the Dijkstra algorithm
//C
graph.dsj(2); graph.showDijkstra(); }}class Graph {
/** * vertex array */
private char[] vertex;
/** * adjacency matrix */
private int[][] matrix;
/** * The set of vertices already visited */
private VisitedVertex vv;
/ / the constructor
public Graph(char[] vertex, int[][] matrix) {
this.vertex = vertex;
this.matrix = matrix;
}
// Display the result
public void showDijkstra(a) {
vv.show();
}
/ / display
public void showGraph(a) {
for (int[] link : matrix) { System.out.println(Arrays.toString(link)); }}/** * Dijkstra algorithm implementation **@paramIndex represents the subscript */ corresponding to the starting vertex
public void dsj(int index) {
vv = new VisitedVertex(vertex.length, index);
update(index);// Update the distance between index vertex and surrounding vertices and precursor vertices
for (int j = 1; j < vertex.length; j++) {
index = vv.updateArr();// Select and return a new access vertex
update(index); // Update the distance between index vertex and surrounding vertices and precursor vertices}}// Update the distance between index subvertex and surrounding vertex and the surrounding vertex's precursor,
private void update(int index) {
int len = 0;
// walk through the matrix[index] rows of our adjacency matrix
for (int j = 0; j < matrix[index].length; j++) {
Len means the sum of the distance from the starting vertex to the index vertex + the distance from the index vertex to the j vertex
len = vv.getDis(index) + matrix[index][j];
// If the j vertex has not been accessed and len is less than the distance from the starting vertex to the j vertex, an update is required
if(! vv.in(j) && len < vv.getDis(j)) {// Update j vertex to index vertex
vv.updatePre(j, index);
// Update the distance from the starting vertex to the j-vertexvv.updateDis(j, len); }}}}/** * The vertex set has been accessed */
class VisitedVertex {
// Records whether each vertex is accessed by 1, which indicates yes. 0 is not accessed, which is dynamically updated
public int[] already_arr;
// Each subscript corresponds to the previous vertex subscript, which is dynamically updated
public int[] pre_visited;
// Record the distance between the starting vertex and all other vertices. For example, if G is the starting vertex, the distance between G and other vertices will be recorded and dynamically updated, and the shortest distance will be stored in dis
public int[] dis;
/ / the constructor
/ * * *@paramLength: number of vertices *@paramIndex: The index of the starting vertex, such as G vertex, is 6 */
public VisitedVertex(int length, int index) {
this.already_arr = new int[length];
this.pre_visited = new int[length];
this.dis = new int[length];
// Initialize the DIS array
Arrays.fill(dis, 65535);
// Set the starting vertex to be visited
this.already_arr[index] = 1;
// Set the starting vertex access distance to 0
this.dis[index] = 0;
}
/** * function: check whether the index vertex is accessed **@param index
* @returnReturn true if yes, false */ otherwise
public boolean in(int index) {
return already_arr[index] == 1;
}
/** * update the distance from the starting vertex to the index vertex **@param index
* @param len
*/
public void updateDis(int index, int len) {
dis[index] = len;
}
/** * function: Update pre to index vertex **@param pre
* @param index
*/
public void updatePre(int pre, int index) {
pre_visited[pre] = index;
}
/** * returns the distance from the starting vertex to the index vertex **@param index
*/
public int getDis(int index) {
return dis[index];
}
/** * continue to select and return A new access vertex, such as G here, is the new access vertex (note not the starting vertex) **@return* /
public int updateArr(a) {
int min = 65535, index = 0;
for (int i = 0; i < already_arr.length; i++) {
if (already_arr[i] == 0&& dis[i] < min) { min = dis[i]; index = i; }}// Update index vertex is accessed
already_arr[index] = 1;
return index;
}
// Display the final result
// To output the case of three arrays
public void show(a) {
System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = = =");
/ / output already_arr
for (int i : already_arr) {
System.out.print(i + "");
}
System.out.println();
/ / output pre_visited
for (int i : pre_visited) {
System.out.print(i + "");
}
System.out.println();
/ / to lose the dis
for (int i : dis) {
System.out.print(i + "");
}
System.out.println();
// In order to see the shortest distance, we handle
char[] vertex = {'A'.'B'.'C'.'D'.'E'.'F'.'G'};
int count = 0;
for (int i : dis) {
if(i ! =65535) {
System.out.print(vertex[count] + "(" + i + ")");
} else {
System.out.println("N "); } count++; } System.out.println(); }}Copy the code