Dijkstra.java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class Dijkstra {

  class VectorAndDistance {

    int vector;
    int distance;

    VectorAndDistance(int vector, int distance) {
      this.vector = vector;
      this.distance = distance;
    }

  }

  interface VectorDistanceSet {

    boolean isEmpty();

    VectorAndDistance removeMin();

    void updateDistance(int vector, int newDistance);

    int getDistance(int vector);

  }

  class SimpleVectorDistanceSet implements VectorDistanceSet {

    private DistanceAndStatus[] elements;
    private int size;

    SimpleVectorDistanceSet(int vectorCount) {
      if (vectorCount < 1)
        throw new IllegalArgumentException("vector count must >= 1");

      elements = new DistanceAndStatus[size = vectorCount];
      for (int i = 0; i < size; i++) {
        elements[i] = new DistanceAndStatus(Integer.MAX_VALUE, false);
      }
    }

    public boolean isEmpty() {
      return size == 0;
    }

    public VectorAndDistance removeMin() {
      if (isEmpty()) throw new IllegalStateException("empty set");
      int minDistance = Integer.MAX_VALUE;
      int minVector = -1;
      for (int i = 0; i < elements.length; i++) {
        if (!elements[i].accessed && elements[i].distance <= minDistance) {
          minDistance = elements[i].distance;
          minVector = i;
        }
      }
      elements[minVector].accessed = true;
      size--;
      return new VectorAndDistance(minVector, minDistance);
    }

    public void updateDistance(int vector, int newDistance) {
      elements[vector] =
          new DistanceAndStatus(newDistance, elements[vector].accessed);
    }

    public int getDistance(int vector) {
      return elements[vector].distance;
    }

  }

  class DistanceAndStatus {

    int distance;
    boolean accessed;

    DistanceAndStatus(int distance) {
      this(distance, true);
    }

    DistanceAndStatus(int distance, boolean accessed) {
      this.distance = distance;
      this.accessed = accessed;
    }

  }

  static class AdjacencyList {

    // start -> [(end, weight)]
    private Map<Integer, List<VectorAndWeight>> connection =
        new HashMap<Integer, List<VectorAndWeight>>();

    AdjacencyList(int[][] adjacencyList) {
      for (int[] edge : adjacencyList) {
        // start, end, weight
        int startVector = edge[0];
        if (!connection.containsKey(startVector)) {
          connection.put(startVector, new ArrayList<VectorAndWeight>());
        }
        connection.get(startVector).add(new VectorAndWeight(edge[1], edge[2]));
      }
    }

    List<Integer> getEndVectorFrom(int startVector) {
      List<Integer> vectors = new ArrayList<Integer>();
      if (connection.containsKey(startVector)) {
        for (VectorAndWeight item : connection.get(startVector)) {
          vectors.add(item.vector);
        }
      }
      return vectors;
    }

    int weight(int startVector, int endVector) {
      if (connection.containsKey(startVector)) {
        for (VectorAndWeight item : connection.get(startVector)) {
          if (item.vector == endVector) return item.weight;
        }
      }
      throw new IllegalArgumentException("no edge between vector ["
          + startVector + "] and vector [" + endVector + "]");
    }

  }

  static class VectorAndWeight {

    int vector;
    int weight;

    VectorAndWeight(int vector, int weight) {
      this.vector = vector;
      this.weight = weight;
    }

  }

  /**
   * Find minimum distance in adjacency list from start vector to end one.
   * 
   * @param adjacencyList
   * @param vectorCount
   * @param startVector
   * @param endVector
   */
  public void findMinDistance(AdjacencyList adjacencyList, int vectorCount,
      int startVector, int endVector) {
    VectorDistanceSet distanceSet = new SimpleVectorDistanceSet(vectorCount);
    int[] previousLink = new int[vectorCount];

    distanceSet.updateDistance(startVector, 0);
    while (!distanceSet.isEmpty()) {
      VectorAndDistance vd = distanceSet.removeMin();
      int u = vd.vector;
      for (int v : adjacencyList.getEndVectorFrom(u)) {
        int weight = adjacencyList.weight(u, v);
        if (distanceSet.getDistance(v) > vd.distance + weight) {
          distanceSet.updateDistance(v, vd.distance + weight);
          previousLink[v] = u;
        }
      }
      if (u == endVector) break;
    }

    int minDistance = distanceSet.getDistance(endVector);
    System.out.println(minDistance);
    if (minDistance == Integer.MAX_VALUE) return;
    printPath(startVector, endVector, previousLink);
  }

  private void printPath(int startVector, int endVector, int[] previousLink) {
    LinkedList<Integer> stack = new LinkedList<Integer>();
    stack.push(endVector);
    int vx = endVector;
    while (previousLink[vx] != startVector) {
      stack.push(previousLink[vx]);
      vx = previousLink[vx];
    }
    stack.push(startVector);
    System.out.println(stack);
  }

  public static void main(String[] args) {
    AdjacencyList adjacencyList = new AdjacencyList(new int[][] {
        {0, 1, 6},
        {0, 2, 3},
        {1, 2, 2},
        {1, 3, 5},
        {2, 3, 3},
        {2, 4, 4},
        {3, 4, 2},
        {3, 5, 3},
        {4, 5, 5}
    });
    Dijkstra dijkstra = new Dijkstra();
    dijkstra.findMinDistance(adjacencyList, 6, 0, 5);
  }

}