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 
    } 
}