Dijkstra's Algorithm for EdgeWeightedGraph

Dijkstra.java

static class Dijkstra {

    int source;
    int v;
    int[] distTo;
    boolean[] marked;
    Edge[] edgeTo;
    EdgeWeightedGraph G;

    public Dijkstra(int source, EdgeWeightedGraph G) {
        this.source = source;
        this.G = G;
        v = G.noOfVertices;
        distTo = new int[v];
        marked = new boolean[v];
        edgeTo = new Edge[v];
        for (int x = 1; x < v; x++) {
            distTo[x] = Integer.MAX_VALUE;
        }

        distTo[source] = 0;

        runDijkistra();
    }

    private void runDijkistra() {
        HashSet<Integer> vertices = new HashSet<Integer>();
        vertices.add(source);
        while (!vertices.isEmpty()) {
            int u = 0;
            int min = Integer.MAX_VALUE;
            for (int k = 1; k < v; k++) {
                if (!marked[k] && distTo[k] < min) {
                    min = distTo[k];
                    u = k;
                }
            }
            marked[u] = true;
            for (Edge edge : G.getAdjEdges(u)) {
                int w = edge.otherVertex(u);
                if (distTo[w] > distTo[u] + edge.getWeight()) {
                    distTo[w] = distTo[u] + edge.getWeight();
                    edgeTo[w] = edge;
                    vertices.add(w);
                }
            }
            vertices.remove(u);
        }
    }

    public ArrayList<Edge> pathTo(int v) {
        ArrayList<Edge> path = new ArrayList<Edge>();
        for (Edge e = edgeTo[v]; e != null; e = edgeTo[e.otherVertex(v)]) {
            path.add(e);
        }
        Collections.reverse(path);
        return path;
    }

    public int distTo(int v) {
        return distTo[v];
    }

    public boolean hasPathTo(int v) {
        return distTo[v] < Integer.MAX_VALUE;
    }

}