Algorithms in Java from Prim's MST to Dijkstra SPT

Question

I am following the code of the Algorithms in Java, Part 5: Graph Algorithms, 3rd Edition book and in page 294 it describes that we can have the classic Dijkstra algorithm by modifying Prim's Minimum Spanning Tree (MST) algorithm (which I tested and works fine) in the following way: change the priority assignment from P = e->wt() the edge weight to P = wt[v] + e->wt() the distance from the source to the edge’s destination. The problem is that when I make the change the condition that follows never evaluates to true and it is understandably so. wt is a double array initialized to e.g. Double.MAX_VALUE therefore no matter what v and w are, this condition will never hold (assuming non negative weights):

P = wt[v] + e->wt();
if (P < wt[w]) { // this can never happen ... bug?
   // ...
} 

I checked the web site of the book and see no errata.

This is my self contained version of the code with a runnable Main with the test case from the book:

UPDATES:

• added initialization line wt[getSource().index] = 0.0; following feedback from one of the answers. The source vertex belongs to the SPT with distance zero.

  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

You get it wrong, since v != w, wt[v] + e->wt() can be smaller than wt[w]. The actual error is that you need to set wt[source] = 0 (dijkstra is single-source shortest path, you need a source!) ! About the book: if they forgot that part, their bad :-P