Graph Algorithms Part II.

public MST getMinimumSpanningTree(int startingVertex) {
        List<Integer> T = new ArrayList<Integer>();
        // T initially contains the startingVertex;
        T.add(startingVertex);

        // Number of vertices
        int numberOfVertices = vertices.size();
        // Parent of a vertex
        int[] parent = new int[numberOfVertices];
        // Initially set the parent of all vertices to -1
        Arrays.fill(parent, -1);

        // Total weight of the tree thus far
        double totalWeight = 0;

        // Clone the priority queue, so to keep the original queue intact
        List<PriorityQueue<WeightedEdge>> queues = deepClone(this.queues);

        // All vertices are found?
        while (T.size() < numberOfVertices) {
            // Search for the vertex with the smallest edge adjacent to
            // a vertex in T
            int v = -1;
            double smallestWeight = Double.MAX_VALUE;
            for (int u : T) {
                while (!queues.get(u).isEmpty() && T.contains(queues.get(u).peek().v)) {
                    // Remove the edge from queues[u] if the adjacent
                    // vertex of u is already in T
                    queues.get(u).remove();
                }

                if (!queues.get(u).isEmpty()) {
                    // Current smallest weight on an edge adjacent to u
                    WeightedEdge edge = queues.get(u).peek();
                    if (edge.weight < smallestWeight) {
                        v = edge.v;
                        smallestWeight = edge.weight;
                        // If v is added to the tree, u will be its parent
                        parent[v] = u;
                    }
                }
            } // End of for

            if (v != -1) {
                T.add(v); // Add a new vertex to the tree
                totalWeight += smallestWeight;
            } else {
                break; // The tree is not connected, a partial MST is found
            }
        } // End of while

        return new MST(startingVertex, parent, T, totalWeight);
    }

	/**
     * Clone an array of queues
     */
    private List<PriorityQueue<WeightedEdge>> deepClone(List<PriorityQueue<WeightedEdge>> queues) {
        List<PriorityQueue<WeightedEdge>> copiedQueues = new ArrayList<PriorityQueue<WeightedEdge>>();

        for (int i = 0; i < queues.size(); i++) {
            copiedQueues.add(new PriorityQueue<WeightedEdge>());
            for (WeightedEdge e : queues.get(i)) {
                copiedQueues.get(i).add(e);
            }
        }

        return copiedQueues;
    }

public ShortestPathTree getShortestPath(int sourceVertex) {
        // T stores the vertices whose path found so far
        List<Integer> T = new ArrayList<Integer>();
        // T initially contains the sourceVertex;
        T.add(sourceVertex);

        // vertices is defined in AbstractGraph
        int numberOfVertices = vertices.size();

        // parent[v] stores the previous vertex of v in the path
        int[] parent = new int[numberOfVertices];
        parent[sourceVertex] = -1; // The parent of source is set to -1

        // cost[v] stores the cost of the path from v to the source
        double[] cost = new double[numberOfVertices];
        for (int i = 0; i < cost.length; i++) {
            cost[i] = Double.MAX_VALUE; // Initial cost set to infinity
        }
        cost[sourceVertex] = 0; // Cost of source is 0

        // Get a copy of queues
        List<PriorityQueue<WeightedEdge>> queues = deepClone(this.queues);

        // Expand T
        while (T.size() < numberOfVertices) {
            int v = -1; // Vertex to be determined
            double smallestCost = Double.MAX_VALUE; // Set to infinity
            for (int u : T) {
                while (!queues.get(u).isEmpty() && T.contains(queues.get(u).peek().v)) {
                    queues.get(u).remove(); // Remove the vertex in queue for u
                }

                if (!queues.get(u).isEmpty()) {
                    WeightedEdge e = queues.get(u).peek();
                    if (cost[u] + e.weight < smallestCost) {
                        v = e.v;
                        smallestCost = cost[u] + e.weight;
                        // If v is added to the tree, u will be its parent
                        parent[v] = u;
                    }
                }
            } // End of for

            if (v != -1) {
                T.add(v); // Add a new vertex to T
                cost[v] = smallestCost;
            } else {
                break; // Graph is not connected, s cannot reach all vertices
            }
        } // End of while

        // Create a ShortestPathTree
        return new ShortestPathTree(sourceVertex, parent, T, cost);
    }

 public ShortestPathTree getShortestPath2(int sourceVertex) {
        // T stores the vertices whose path found so far
        List<Integer> T = new ArrayList<Integer>();

        // T initially contains the sourceVertex;
        T.add(sourceVertex);

        // vertices is defined in AbstractGraph
        int numberOfVertices = vertices.size();

        // parent[v] stores the previous vertex of v in the path
        int[] parent = new int[numberOfVertices];
        // The parent of source is set to -1
        parent[sourceVertex] = -1;

        // cost[v] stores the cost of the path from v to the source
        double[] cost = new double[numberOfVertices];
        Arrays.fill(cost, Double.MAX_VALUE);

        // Cost of source is 0
        cost[sourceVertex] = 0;

        // Get a copy of queues
        List<PriorityQueue<WeightedEdge>> queues = deepClone(this.queues);

        // Set cost for the neighbors of sourceVertex
     	// diff from method1
        while (!queues.get(sourceVertex).isEmpty()) {
            WeightedEdge e = queues.get(sourceVertex).poll();
            cost[e.v] = e.weight;
            parent[e.v] = sourceVertex;
        }

        // Expand T
        while (T.size() < numberOfVertices) {
            // Find smallest cost v in V - T
            int v = -1; // Vertex to be determined
            double currentMinCost = Double.MAX_VALUE;
            for (int i = 0; i < getSize(); i++) {
                if (!T.contains(i) && cost[i] < currentMinCost) {
                    currentMinCost = cost[i];
                    v = i;
                }
            }

            if (v != -1) {
                T.add(v); // Add a new vertex to T

                // Adjust cost[u] for u that is adjacent to v and u in V - T
                while (!queues.get(v).isEmpty()) {
                    WeightedEdge e = queues.get(v).poll();
                    if (!T.contains(e.v) && cost[e.v] > cost[v] + e.weight) {
                        cost[e.v] = cost[v] + e.weight;
                        parent[e.v] = v;
                    }
                }
            } else {
                break; // s cannot reach to all vertices
            }
        } // End of while

        // Create a ShortestPathTree
        return new ShortestPathTree(sourceVertex, parent, T, cost);
    }