Example of Dijkstra algorithm based on Java implementation

This paper introduces the implementation of Dijkstra algorithm based on Java in the form of an example.

Dijkstra proposed an algorithm to generate the shortest path to each vertex according to the increasing order of the path length between each vertex and the source point v. That is, the shortest path with the shortest length is found first, then the shortest path with the shortest length is found by referring to it, and so on, until the shortest paths from the source point v to other vertices are all found.
Its code implementation is shown as follows:

package com.algorithm.impl;

public class Dijkstra {
 private static int M = 10000; //That the 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(" from "+start+" Set out to "+i+" The shortest distance is: "+shortPath[i]); 
 }
 
 public static int[] dijkstra(int[][] weight, int start) {
 //Accept the weight matrix of a directed graph, and the starting point number start (number from 0, vertices in the array)
    //Returns an int[] array representing the shortest path length from start to it
 int n = weight.length;      //The number of vertices
 int[] shortPath = new int[n];  //Save the shortest path from start to each of the other points
 String[] path = new String[n];  //Saves a string representation of the shortest path from start to each of the other points
 for(int i=0;i<n;i++) 
  path[i]=new String(start+"-->"+i); 
 int[] visited = new int[n];   //Indicates whether the shortest path of the vertex has been found, and 1 indicates that it has been found
 
 //Initialization, the first vertex is already figured out
 shortPath[start] = 0;
 visited[start] = 1;
 
 for(int count = 1; count < n; count++) {   //I'm going to add n minus 1 vertices
  int k = -1;        //Select the 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 found, and the shortest path to start is dmin
  shortPath[k] = dmin;
  visited[k] = 1;
  
  //With k as the intermediate point, the distance from start to the unvisited points is fixed
  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(" from "+start+" Set out to "+i+" The shortest path is: "+path[i]);
 }
 System.out.println("====================================="); 
 return shortPath;
 }
}

The running result of this program is:

 from 0 Set out to 0 The shortest path is: 0-->0
 from 0 Set out to 1 The shortest path is: 0-->1
 from 0 Set out to 2 The shortest path is: 0-->3-->2
 from 0 Set out to 3 The shortest path is: 0-->3
 from 0 Set out to 4 The shortest path is: 0-->3-->2-->4
=====================================
 from 0 Set out to 0 The shortest distance is: 0
 from 0 Set out to 1 The shortest distance is: 10
 from 0 Set out to 2 The shortest distance is: 50
 from 0 Set out to 3 The shortest distance is: 30
 from 0 Set out to 4 The shortest distance is: 60