給Dijkstra算法的Prims算法

Question

我想讓我現有的Prim算法的實現跟蹤距離源的距離。由於prim和Dijkstra算法幾乎相同。我無法弄清楚我錯在哪裏。

我知道問題是什麼，但無法弄清楚。

這是我的代碼，我如何修改它以打印從源到所有其他頂點的最短距離。最短距離存儲在陣列命名：DIST []

代碼：

package Graphs; 

import java.util.ArrayList; 

public class Prims { 

    static int no_of_vertices = 0; 

    public static void main(String[] args) { 
     int[][] graph = {{0, 2, 0, 6, 0}, 
       {2, 0, 3, 8, 5}, 
       {0, 3, 0, 0, 7}, 
       {6, 8, 0, 0, 9}, 
       {0, 5, 7, 9, 0}, 
       }; 
     no_of_vertices = graph.length; 
     int [][] result = new int [no_of_vertices][no_of_vertices]; 
     boolean[] visited = new boolean[no_of_vertices]; 
     int dist[] = new int[no_of_vertices]; 
     for (int i = 0; i < no_of_vertices; i++) 
      for (int j = 0; j < no_of_vertices; j++) { 
       result[i][j]= 0; 
       if (graph[i][j] == 0) { 
        graph[i][j] = Integer.MAX_VALUE; 
       } 
      } 

     for (int i = 0; i < no_of_vertices; i++) { 
      visited[i] = false; 
      dist[i] = 0; 

     } 
     ArrayList<String> arr = new ArrayList<String>(); 
     int min; 
     visited[0] = true; 
     int counter = 0; 
     while (counter < no_of_vertices - 1) { 
      min = 999; 
      for (int i = 0; i < no_of_vertices; i++) { 
       if (visited[i] == true) { 
        for (int j = 0; j < no_of_vertices; j++) { 
         if (!visited[j] && min > graph[i][j]) { 
          min = graph[i][j]; 
          dist[i] += min; // <------ Problem here 
          visited[j] = true; 
          arr.add("Src :" + i + " Destination : " + j 
            + " Weight : " + min); 
         } 
        } 
       } 
      } 
      counter++; 
     } 


     for (int i = 0; i < no_of_vertices; i++) { 
      System.out.println("Source : 0" + " Destination : " + i 
        + " distance : " + dist[i]); 
     } 

     for (String str : arr) { 
      System.out.println(str); 
     } 
    } 
} 

有一個在距離陣列的計算的錯誤，因爲它忘記從源添加到目標的任何中間節點的距離。

Answer 1

for (int j = 0; j < no_of_vertices; j++) { 
    if (!visited[j] && min > graph[i][j]) { 
     min = graph[i][j]; 
     dist[i] += min; // <------ Problem here 

當然中間邊緣不會被添加，因爲您只添加當前邊緣。你可能想要這樣的東西：

if (dist[i] + graph[i][j] < dist[j]) 
    dist[j] = dist[i] + graph[i][j]; 

並擺脫min變量。

雖然你的算法看起來不正確。你應該在每一步選擇節點的最小值爲d[]，然後按照我上面寫的那樣更新該節點的鄰居，然後將其標記爲「摘下」，然後再次選取它。