Dijkstra算法

/**
 * Dijkstra's algorithm
 * @param d matrix of legths, position [0 1] = 2 means that from node 0 leads an edge to node 1 of length 2
 * @param from root node
 * @return tree an ancestors (denotes path from the node to the root node)
 */
procedure int[] doDijkstra(d, from) {
    //insert all nodes to the priority queue, node from has a distance 0, all others infinity
    Q = InsertAllNodesToTheQueue(d, from)
    CLOSED = {} //closed nodes - empty set
    predecessors = new array[d.nodeCount] //array of ancestors

    while !Q.isEmpty() do
        node = Q.extractMin()
        CLOSED.add(node) //close the node

        //contract distances
        for a in Adj(node) do //for all descendants
            if !CLOSED.contains(a) //if the descendatn was not closed yet
                //and his distance has decreased               
                if Q[node].distance + d[node][a] < Q[a].distance
                    //zmen prioritu (vzdalenost) uzlu
                    Q[a].distance = Q[node].distance + d[node][a]
                    //change its ancestor
                    predecessors[a] = node   

    return predecessors



	/**
	 * Dijkstra's algorithm
	 * @param d matrix of lengths (Integer.MAX_VALUE if there is no edge between the nodes)
	 * @param from root node
	 * @return tree an ancestors (denotes path from the node to the root node)
	 */
	public static int[] doDijkstra(int[][] d, int from) {
	    Set<Integer> set = new HashSet<Integer>();
	    set.add(from);

	    boolean[] closed = new boolean[d.length];
	    int[] distances = new int[d.length];
	    for (int i = 0; i < d.length; i++) {
	        if (i != from) {
	            distances[i] = Integer.MAX_VALUE;
	        } else {
	            distances[i] = 0;
	        }
	    }


	    int[] predecessors = new int[d.length];
	    predecessors[from] = -1;

	    while (!set.isEmpty()) {
	        //find the nearest node
	        int minDistance = Integer.MAX_VALUE;
	        int node = -1;
	        for(Integer i : set){
	            if(distances[i] < minDistance){
	                minDistance = distances[i];
	                node = i;
	            }
	        }

	        set.remove(node);
	        closed[node] = true;

	        //contract the distances
	        for (int i = 0; i < d.length; i++) {
	            //edge exists
	            if (d[node][i] != Integer.MAX_VALUE) {
	                if (!closed[i]) {
	                    //the path length decreased using the ancestor node
	                    if (distances[node] + d[node][i] < distances[i]) {
	                        distances[i] = distances[node] + d[node][i];
	                        predecessors[i] = node;
	                        set.add(i);
	                    }
	                }
	            }
	        }
	    }
	    return predecessors;
	}