Java实现Dijkstra算法并打印路径详细代码

import java.util.Scanner; //Scanner Function to take in the Input Values
  
public class Dijkstra
{
     static Scanner scan; // scan is a Scanner Object
  
     public static void main(String[] args)
     {
         int [] preD = new int [ 5 ];
         int min = 999 , nextNode = 0 ; // min holds the minimum value, nextNode holds the value for the next node.
         scan = new Scanner(System.in);
         int [] distance = new int [ 5 ]; // the distance matrix
         int [][] matrix = new int [ 5 ][ 5 ]; // the actual matrix
         int [] visited = new int [ 5 ]; // the visited array
  
         System.out.println( "Enter the cost matrix" );
  
         for ( int i = 0 ; i < distance.length; i++)
         {
             visited[i] = 0 ; //initialize visited array to zeros
             preD[i] = 0 ;
  
             for ( int j = 0 ; j < distance.length; j++)
             {
                 matrix[i][j] = scan.nextInt(); //fill the matrix
                 if (matrix[i][j]== 0 )
                     matrix[i][j] = 999 ; // make the zeros as 999
             }
         }
  
         distance = matrix[ 0 ]; //initialize the distance array
         visited[ 0 ] = 1 ; //set the source node as visited
         distance[ 0 ] = 0 ; //set the distance from source to source to zero which is the starting point
  
         for ( int counter = 0 ; counter < 5 ; counter++)
         {
             min = 999 ;
             for ( int i = 0 ; i < 5 ; i++)
             {
                 if (min > distance[i] && visited[i]!= 1 )
                 {
                     min = distance[i];
                     nextNode = i;
                 }
             }
  
             visited[nextNode] = 1 ;
             for ( int i = 0 ; i < 5 ; i++)
             {
                 if (visited[i]!= 1 )
                 {
                     if (min+matrix[nextNode][i] < distance[i])
                     {
                         distance[i] = min+matrix[nextNode][i];
                         preD[i] = nextNode;
                     }
  
                 }
  
             }
  
         }
  
         for ( int i = 0 ; i < 5 ; i++)
             System.out.print( "|" + distance[i]);
  
         System.out.println( "|" );
  
         int j;
         for ( int i = 0 ; i < 5 ; i++)
         {
             if (i!= 0 )
             {
  
                 System.out.print( "Path = " + i);
                 j = i;
                 do
                 {
                     j = preD[j];
                     System.out.print( " <- " + j);
                 }
                 while (j != 0 );
             }
             System.out.println();
         }
     }
}

该程序由Raj Miglani贡献。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。