Java中的最短路徑實現

Question

我正在使用一個鄰接矩陣，並嘗試創建一個函數，在圖中找到最短路徑。我試圖修改我用來編寫最小生成樹函數的Prim算法。

public static int shortest(int first, int last) throws Exception{ 
       int weight[] = new int[Nodes.length]; //keeps track of the weights of the added edges 
       int path[] = new int[Nodes.length]; //keeps track of the nodes in the path 
       boolean visited[] = new boolean[Nodes.length]; //keeps track of nodes visited 
       int current; 
       int total; 
       int minWeight; 
       int nodes = Nodes.length; 
       int i; 

       for (i=0;i<nodes;i++){ //initialization 
        path[i]=0; 
        visited[i]=false; 
        weight[i]=32767; //largest short int 
       } 

       current=first; 
       weight[current]=0; 
       total=1; 
       visited[current]=true; 
       path[0]=current; 

       while(total!=nodes){ 
        for(i=1;i<nodes;i++){ 
         if(AMatrix[current][i] != 0 && visited[i]==false && weight[i]>AMatrix[current][i]){  
           weight[i]=AMatrix[current][i]; 
            path[i]=current; 
         } 
        } 
        minWeight=32767; 
        for(i=1;i<nodes;i++){ 
         if(visited[i]==false && weight[i]<minWeight){ 
          minWeight=weight[i]; 
          current=i; 
         } 
        } 
        write("current = "+ current); 
        visited[current]=true; 
        total++; 

        if(current == last){ 
         path[total-1]=current; 
         for(i=1;i<total;i++){ 
          write("includes the node "+Nodes[path[i]]); 
         } 

         minWeight=0; 
         int j=1; 
         for(i=2;i<total;i++){ 
          write("The weight from "+Nodes[path[j]]+" to "+Nodes[path[i]]+" is "+AMatrix[path[j]][path[i]]); 
          minWeight = minWeight+AMatrix[path[j]][path[i]]; 
          write("min weight= "+minWeight); 
          j++; 
         } 
         return minWeight; 
        } 
       } 

       return -1; 
     } 

它的工作原理與我把它那裏，我開始與第一節點的輸入之一，但如果我試着以不同的節點，它創建一個連接未實際連接的兩個節點的路徑。我盯着這麼久，我看不出爲什麼這樣做。最小的生成樹工作得很好，我認爲這將是一個簡單的修改，但它不起作用。

我實際上認爲這樣做有很多錯誤，例如如果我嘗試打印出從0開始的路徑數組元素，它會打印出第一個元素兩次，所以我確信我'我犯了很多錯誤，但那是現在對我來說公然明顯的錯誤。

AMatrix是我的鄰接矩陣，Nodes是我每個節點的矩陣。寫是我寫的功能，寫入輸出文件。

Answer 1

數組有零基索引。但是，你的前兩個循環，從1開始：

爲（i = 1;我<節點;我++）

因此，這將有可能導致這一事實，當你開始first=0的作品，因爲在你的鄰接矩陣AMatrix[current][i] != 0對角線（當前== I）可能是0。但是，如果你有其他的值從0開始的算法，你缺少一個節點：0

而且，只是一些提示：

• 你說：「weight [i] = 32767; //最大短整數「，但這是最大的短，2^15 - 1，這是更好的初始化像這樣：weight[i] = Short.MAX_VALUE;。如果你想最大的int，它是類似的：weight[i] = Integer.MAX_VALUE;
• 最好不要使用靜態一切都很簡單，它不是簡單的測試，它不是面向對象的，你也許可以使用JUnit編寫單元測試，或者像Domi在評論中所說的那樣，嘗試調試你的代碼（例如使用eclipse調試器）
• 如果你沒有自己寫代碼，那麼代碼有點難以理解/理解，因此，添加註釋，例如在循環上方解釋它的作用。代碼的可讀性比編寫代碼更重要，因爲你會閱讀代碼幾次，但你只寫一次。