This article introduces the Dijkstra algorithm based on Java in the form of examples. I believe it will be helpful to readers in studying and learning data structure domain algorithms.
Dijkstra proposed an algorithm to generate the shortest path to each vertex in increasing order of the path length between each vertex and the source point v. That is, first find the shortest path with the shortest length, and then use it to find the shortest path with the next shortest length, and so on, until all the shortest paths from the source point v to other vertices are found.
The code implementation is as follows:
package com.algorithm.impl; public class Dijkstra { private static int M = 10000; //This road is blocked public static void main(String[] args) { int[][] weight1 = {//Adjacency matrix {0,3 ,2000,7,M}, {3,0,4,2,M}, {M,4,0,5,4}, {7,2,5,0,6}, {M,M,4,6,0} }; int[][] weight2 = { {0,10,M,30,100}, {M,0,50,M,M}, {M,M,0, M,10}, {M,M,20,0,60}, {M,M,M,M,0} }; int start=0; int[] shortPath = dijkstra(weight2,start); for(int i = 0;i < shortPath.length;i++) System.out.println("The shortest distance from "+start+" to "+i+" is: "+shortPath[i ]); } public static int[] dijkstra(int[][] weight, int start) { //Accepts a weight matrix of a directed graph, and a starting point number start (numbered from 0, the vertex is stored in the array) //Returns an int[] array, indicating the length of the shortest path from start to it int n = weight.length ; //Number of vertices int[] shortPath = new int[n]; //Save the shortest path from start to other points String[] path = new String[n]; //Save the shortest path from start to other points String representation for(int i=0;i<n;i++) path[i]=new String(start+"-->"+i); int[] visited = new int[n]; //Mark whether the shortest path to the current vertex has been Find, 1 means it has been found //Initialization, the first vertex has been found shortPath[start] = 0; visited[start] = 1; for(int count = 1; count < n; count++) { //To add n-1 vertices int k = -1; //Select an unmarked vertex closest to the initial vertex start int dmin = Integer.MAX_VALUE; for(int i = 0; i < n; i++) { if(visited[i] == 0 && weight[start][i] < dmin) { dmin = weight[start][i]; k = i; } } //Mark the newly selected vertex as the shortest path has been found, and the shortest path to start is dmin shortPath[k] = dmin; visited[k] = 1; //With k as the middle point, correct the path from start to Distance of unvisited points for(int i = 0; i < n; i++) { if(visited[i] == 0 && weight[start][k] + weight[k][i] < weight[start] [i]) { weight[start][i] = weight[start][k] + weight[k][i]; path[i] = path[k] + "-->" + i; } } } for(int i = 0; i < n; i++) { System.out.println("The shortest path from "+start+" to "+i+" is: "+path[i]); } System.out.println("====================================="); return shortPath; }}The result of running this program is:
The shortest path from 0 to 0 is: 0-->0 The shortest path from 0 to 1 is: 0-->1 The shortest path from 0 to 2 is: 0-->3-->2 from The shortest path from 0 to 3 is: 0-->3 The shortest path from 0 to 4 is: 0-->3-->2-->4==== =================================The shortest distance from 0 to 0 is: 0 from 0 to 1 The shortest distance from 0 to 2 is: 50 The shortest distance from 0 to 3 is: 30 The shortest distance from 0 to 4 is: 60