fork(6) download
copy 
  1. 	/* package whatever; // don't place package name! */
  2.  
  3. import java.util.Scanner; 
  4.  
  5. /* Name of the class has to be "Main" only if the class is public. */
  6. class Ideone
  7. {
  8.  
  9. 	static Scanner scan; 
  10.  
  11. 	public static void main (String[] args) throws java.lang.Exception
  12. 	{
  13.  
  14. 		// declare 
  15.  
  16. 		int [][] matrix = new int [8][8]; 
  17. 		int [] distance = new int [8]; int [] pred = new int [8]; int [] visited = new int [8]; 
  18. 		int min = 9999 ; int nextnode = 0 ; 
  19.  
  20. 	scan = new Scanner(System.in);
  21.  
  22.  
  23.  
  24.  
  25.  
  26. 	// input
  27.  
  28. 	for ( int i = 0 ; i< 8 ; i++)
  29. 	{
  30. 			pred [i] = 0 ; 
  31. 			visited[i] = 0 ; 
  32.  
  33. 		 for ( int j = 0 ; j< 8 ; j++)
  34.  
  35. 		 	{ 
  36. 		 		matrix[i][j] = scan.nextInt(); 
  37. 		 		if (matrix[i][j] ==0 )matrix[i][j] = 9999; 
  38. 		 	}
  39. 	}
  40.  
  41.  
  42.  
  43.  
  44.  
  45.  
  46. 			//dj's algo 
  47.  
  48. visited[0] = 1; 
  49. distance = matrix[0]; 
  50. distance[0]=0; 
  51.  
  52.  
  53. for ( int c= 0 ; c<8;c++)//all ndes
  54. { 
  55. min = 9999; 
  56.  
  57.  
  58. for ( int i = 0 ; i< 8 ; i++) // updat distances 
  59. {
  60. 	if ( min > distance [i] && visited[i] !=1 )// if reachable and never visited 
  61. 	{ 
  62. 		nextnode=i; 
  63. 		min = distance[i]; 
  64. 	}
  65. }
  66.  
  67.  
  68. visited[nextnode] =1; 
  69.  
  70. for ( int i =0 ; i < 8 ; i++)
  71. {
  72. 	if ( visited[i]!=1){
  73.  
  74. 		if ( min + matrix[nextnode][i] < distance[i])
  75. 		{
  76. 			distance[i] = min + matrix[nextnode][i]; 
  77. 			pred[i] = nextnode; 
  78. 		}
  79. 	}
  80. }
  81.  
  82.  
  83.  
  84. }
  85.  
  86.  
  87.  
  88.  
  89. // output 
  90.  
  91. for ( int i = 0 ; i< 8 ; i++)
  92. { 
  93.  
  94. System.out.print("|" + distance[i]); 
  95.  
  96. }System.out.print("|"); 
  97.  
  98.  
  99.  
  100.  
  101.  
  102. int j; 
  103. for ( int i = 0; i < 8 ; i++)
  104. 	{ 
  105. if ( i!=0){
  106.  
  107.  
  108. 			String s = numtocharez(i); 
  109. 			System.out.print("Path = "+ s); 
  110.  
  111. 			j=i; 
  112. 			do { 
  113. 				j = pred[j]; s= numtocharez(j);
  114. 				System.out.print(" <- " + s); 
  115. 			}while ( j!=0);
  116.  
  117. 	} 
  118. System.out.println(); 
  119.  
  120. }
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
  131. 	}
  132.  
  133.  
  134. public static String numtocharez(int i){return i < 25 && i > -1 ? String.valueOf((char)(i+65)) : null ;}
  135. }
Success #stdin #stdout 0.14s 321344KB
comments (?)
stdin
copy 
   0  25 0  85 0  0  105 0 
   0  0  0  0  0  15 0  0 
   0  00 0  55 0  60 0  20 
   0  00 55 0  0 0  35  0
  0  30 00 00  0 0  50 0 
 0   0 15 40 0  0   0  0
 25  0  0 0  0   0   0  0
 0   0  0  0  0  0  0  0
stdout
copy 
|0|25|55|80|9999|40|105|75|
Path = B <- A
Path = C <- F <- B <- A
Path = D <- F <- B <- A
Path = E <- A
Path = F <- B <- A
Path = G <- A
Path = H <- C <- F <- B <- A
https://ideone.com/5g4tG1
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!