从Prim的MST到Dijkstra的Java算法SPT

Question

我在关注Algorithms in Java, Part 5: Graph Algorithms, 3rd Edition书中的code，在第294页中，它描述了我们可以通过修改Prim的最小生成树（MST）算法来获得经典的Dijkstra算法工作正常）：将优先级从P = e->wt()的边缘权重改为P = wt[v] + e->wt()从源到边缘目标的距离。问题是，当我进行更改时，以下的条件永远不会评估为true，这是可以理解的。 wt是一个初始化为例如Double.MAX_VALUE因此无论什么v和w是，这种情况再也不会担任（假定非负权重）：

​​

我查书的网站，并没有看到勘误表。

这是我自包含的代码的版本可运行的主从书测试用例：

更新：

• 添加以下从其中一个答案反馈起始线wt[getSource().index] = 0.0;。源顶点属于距离为零的SPT。

  import java.util.*; 
  
  public class AdjacencyList { 
      //============================================================= 
      // members 
      //============================================================= 
      private static class Edge { 
       int source; 
       int target; 
       double weight; 
      }; 
      private static class Vertex { 
       int index; 
       String name; 
       List<Edge> edges = new ArrayList<Edge>(); 
       public Vertex(int index, String name) { 
        this.index = index; 
        this.name = name; 
       } 
      }; 
      private static final int UNDEFINED = -1; 
      private int edgesCount = 0; 
      private final Vertex[] vertices; 
      private final boolean digraph; 
      private int orderCount; 
  
      //============================================================= 
      // public 
      //============================================================= 
      public AdjacencyList(int verticesCount, boolean digraph) { 
       this.vertices = new Vertex[verticesCount]; 
       this.digraph = digraph; 
      } 
  
      public Vertex createVertex(int index) { 
       return createVertex(index, String.valueOf(index)); 
      } 
  
      public Vertex createVertex(int index, String name) { 
       Vertex vertex = new Vertex(index, name); 
       vertex.index = index; 
       vertex.name = name; 
       vertices[index] = vertex; 
  
       return vertex; 
      } 
  
      public Edge addEdge(int begin, int end, double weight) { 
       return addEdge(vertices[begin], vertices[end], weight); 
      } 
  
      public Edge addEdge(Vertex begin, Vertex end, double weight) { 
       edgesCount++; 
       Edge edge = new Edge(); 
       edge.source = begin.index; 
       edge.target = end.index; 
       edge.weight = weight; 
       vertices[begin.index].edges.add(edge); 
       if (!digraph) { 
        Edge reverse = new Edge(); 
        reverse.source = end.index; 
        reverse.target = begin.index; 
        reverse.weight = edge.weight; 
        vertices[end.index].edges.add(reverse); 
       } 
       return edge; 
      } 
  
      // inefficient find edge O(V) 
      public Edge findEdge(int begin, int end) { 
       Edge result = null; 
       Vertex vertex = vertices[begin]; 
       List<Edge> adjacency = vertex.edges; 
       for (Edge edge : adjacency) { 
        if (edge.target == end) { 
         result = edge; 
         break; 
        } 
       } 
       return result; 
      } 
  
      // inefficient remove edge O(V) 
      public void removeEdge(int begin, int end) { 
       edgesCount--; 
       removeOneEdge(begin, end); 
       if (!digraph) { 
        removeOneEdge(end, begin); 
       } 
      } 
  
      public final Vertex[] getVertices() { 
       return vertices; 
      } 
  
      public int getVerticesCount() { 
       return vertices.length; 
      } 
  
      public int getEdgesCount() { 
       return edgesCount; 
      } 
  
      public Vertex getSource() { 
       return vertices[0]; 
      } 
  
      public Vertex getSink() { 
       return vertices[vertices.length - 1]; 
      } 
  
      public void dijkstra() { 
       int verticesCount = getVerticesCount(); 
       double[] wt = new double[verticesCount]; 
       for (int i = 0; i < wt.length; i++) { 
        wt[i] = Double.MAX_VALUE; 
       } 
       wt[getSource().index] = 0.0; 
       Edge[] fr = new Edge[verticesCount]; 
       Edge[] mst = new Edge[verticesCount]; 
       int min = -1; 
       Edge edge = null; 
       for (int v = 0; min != 0; v = min) { 
        min = 0; 
        for (int w = 1; w < verticesCount; w++) { 
         if (mst[w] == null) { 
          double P = 0.0; 
          edge = findEdge(v, w); 
          if (edge != null) { 
           if ((P = wt[v] + edge.weight) < wt[w]) { 
            wt[w] = P; 
            fr[w] = edge; 
           } 
          } 
  
          if (wt[w] < wt[min]) { 
           min = w; 
          } 
         } 
        } 
  
        if (min != 0) { 
         mst[min] = fr[min]; 
        } 
       } 
  
       for (int v = 0; v < verticesCount; v++) { 
        if (mst[v] != null) { 
         System.out.print(mst[v].source + "->" + mst[v].target + " "); 
        } 
       } 
      } 
  
      public void pushRelabel() { 
       // TODO 
      } 
  
      //============================================================= 
      // private 
      //============================================================= 
  
      private void removeOneEdge(int begin, int end) { 
       Vertex beginVertex = vertices[begin]; 
       List<Edge> adjacency = beginVertex.edges; 
       int position = -1; 
       for (int i = 0; i < adjacency.size(); i++) { 
        if (adjacency.get(i).target == end) { 
         position = i; 
         break; 
        } 
       } 
       if (position != -1) { 
        adjacency.remove(position); 
       } 
      } 
  
      private static AdjacencyList createDijkstraGraph() { 
       int numberOfVertices = 6; 
       boolean directed = true; 
       AdjacencyList graph = new AdjacencyList(numberOfVertices, directed); 
       for (int i = 0; i < graph.getVerticesCount(); i++) { 
        graph.createVertex(i); 
       } 
       graph.addEdge(0, 1, .41); 
       graph.addEdge(1, 2, .51); 
       graph.addEdge(2, 3, .50); 
       graph.addEdge(4, 3, .36); 
       graph.addEdge(3, 5, .38); 
       graph.addEdge(3, 0, .45); 
       graph.addEdge(0, 5, .29); 
       graph.addEdge(5, 4, .21); 
       graph.addEdge(1, 4, .32); 
       graph.addEdge(4, 2, .32); 
       graph.addEdge(5, 1, .29); 
       return graph; 
      } 
  
      /** 
      * Test main 
      * 
      * @param args 
      */ 
      public static void main(String[] args) { 
       // build the graph and test dijkstra shortest path 
       AdjacencyList directedDijkstra = createDijkstraGraph(); 
       // expected: 
       System.out.println("\n\n*** testing dijkstra shortest path"); 
       directedDijkstra.dijkstra(); 
      } 
  } 
  

Answer 1

你弄错了，因为V！= W，重量[V] + E->重量（）可以比重量[W]小。实际的错误是你需要设置wt[source] = 0（dijkstra是单源最短路径，你需要一个源！）！关于该书：如果他们忘记了那部分，他们的不好:-P