锐客网

  1. 首页 > 生活百科 > it技术 > >

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

IT知识算法数据结构路径覆盖打印路径

import java.util.Scanner; //Scanner Function to take in the Input Valuespublic class Dijkstra { static Scanner scan; // scan is a Scanner Objectpublic 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 arraySystem.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 pointfor ( 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(); } } }

【Java实现Dijkstra算法并打印路径详细代码】该程序由Raj Miglani贡献。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。

    推荐阅读


    上一篇：Node.js如何使用fs.writeFile()方法（代码实例）

    下一篇：jQuery如何使用星号*选择器（代码实例）