Java最短路径通用解决方案

Question

'p'是节点的数量。所以现在在我的解决方案中，用户必须键入所有的矩阵元素，在7个节点的情况下，49个数字。我不想这样。我想问用户从一点到另一点的距离。对不起，在我的程序中的奇怪的名字，他们在我的语言。 latogatott =走访，TAV =距离

package legrovidebb_ut; 

import java.util.Scanner; 

public class Legrovidebb_ut { 

public static void main (String[] args) { 

    Scanner scan = new Scanner(System.in); 

     System.out.println("Adja meg a pontok szamat: "); 

    int p; 

    p = scan.nextInt(); 

    int[][] matrix = new int [p][p]; 
    int[] tav = new int[p]; 
    int[] latogatott = new int[p]; 
    int[] pre = new int[p]; 
    int min; 
    int nextNode = 0; 


    System.out.println("Enter the matrix!"); 


    for (int i=0; i<p; i++){ 

     latogatott[i]=0; 

     pre[i]=0; 

     for (int j=0;j<p;j++){ 

      matrix[i][j] = scan.nextInt(); 
      if(matrix[i][j]== 0) 
       matrix[i][j]=999; 
     } 
    } 
    tav = matrix[0]; 
    tav[0]=0; 
    latogatott[0]=1; 

    for (int i=0;i<p;i++){ 
     min=999; 

    for(int j=0;j<p;j++){ 
     if(min>tav[j] && latogatott[j]!=1){ 

      min=tav[j]; 
      nextNode=j; 
     } 
    } 
    latogatott[nextNode]=1; 

    for(int c=0;c<p;c++){ 
     if(latogatott[c]!=1){ 
      if(min+matrix[nextNode][c]<tav[c]){ 
       tav[c]=min+matrix[nextNode][c]; 
       pre[c]=nextNode; 
      } 
     } 
    } 
    } 
    for (int i=0;i<p;i++){ 
     System.out.print("|" + tav[i]); 
    } 
    System.out.println("|"); 

    for(int i=0;i<p;i++){ 
     int j; 
     System.out.print("Ut: " + (i+1)); 
     j=i; 

     do{ 
      j=pre[j]; 
      System.out.println(" <- " + (j+1)); 
     }while(j!=0); 
     System.out.println(); 
    } 
} 

}

Answer 1

如果是无向图，你希望用户输入每两个节点之间的距离（如您的评论说），你将需要一个循环通过所有的节点和另一个循环通过所有其他节点，因为2-1距离不需要，如果你有1-2的距离：

for(int i = 0; i < p; i++) { 
    for(int k = i+1; k < p; k++) { 
    // ask user for distance between i and k 
    } 
}