Shortest path of Dijkstra algorithm

Question

I want to implement an iterator for the shortest path in my edge weighted graph.

public class Graph<T> implements GraphADT<T> {

    protected final int DEFAULT_CAPACITY = 10;
    protected int numVertices; // number of vertices in the graph
    protected boolean[][] adjMatrix; // adjacency matrix
    protected T[] vertices; // values of vertices
    protected double weight[][];

I tried many implementation and even try my own, but I think I don't understand the logic off Dijkstra algorithm yet, can anyone explain to me or give their implemention on Java

Here is my attempt to make an in implementation

public Iterator<T> iteratorShortestPathW1(int startIndex, int targetIndex) {
    ArrayUnorderedList<T> resultList = new ArrayUnorderedList<T>();
    if (!indexIsValid(startIndex) || !indexIsValid(targetIndex)) {
        return resultList.iterator();
    }

    Iterator<T> it = iteratorShortestPathW2(startIndex,
            targetIndex);
    while (it.hasNext()) {
        resultList.addToRear(vertices[((Integer) it.next()).intValue()]);
    }
    return resultList.iterator();
}

public Iterator<T> iteratorShortestPathW(T startVertex, T targetVertex) {
    return iteratorShortestPathW1(getIndex(startVertex),
            getIndex(targetVertex));
}

protected Iterator<T> iteratorShortestPathW2(int startIndex, int targetIndex) {
    int index = startIndex;
    int[] tamcaminho = new int[numVertices];
    int[] predecessor = new int[numVertices];
    LinkedQueue<Integer> traversalQueue = new LinkedQueue<Integer>();
    ArrayUnorderedList<Integer> resultList = new ArrayUnorderedList<Integer>();

    if (!indexIsValid(startIndex) || !indexIsValid(targetIndex) || (startIndex == targetIndex)) {
        return (Iterator<T>) resultList.iterator();
    }

    boolean[] visited = new boolean[numVertices];
    for (int i = 0; i < numVertices; i++) {
        visited[i] = false;
    }

    traversalQueue.enqueue(startIndex);
    visited[startIndex] = true;
    tamcaminho[startIndex] = 0;
    predecessor[startIndex] = -1;

    while (!traversalQueue.isEmpty() && (index != targetIndex)) {
        System.out.print("acima");
        index = traversalQueue.dequeue();
        int menor = 999;
        for (int i = 0; i < numVertices; i++) {
            if (adjMatrix[index][i] && !visited[i]) {
                tamcaminho[i] = (int) weight[index][i];

                if (menor > tamcaminho[i]) {
                    menor = tamcaminho[i];
                }
            }
        }

        for (int i = 0; i < numVertices ; i++) {
            if (tamcaminho[i] == menor) {                  
                System.out.print("abaixo");
                visited[index] = true;
                traversalQueue.enqueue(i);
                predecessor[i] = index;

            }
        }
    }
    if (index != targetIndex) {
        return (Iterator<T>) resultList.iterator();
    }

    LinkedStack<Integer> stack = new LinkedStack<Integer>();
    index = targetIndex;
    stack.push(new Integer(index));
    do {
        index = predecessor[index];
        stack.push(new Integer(index));
    } while (index != startIndex);

    while (!stack.isEmpty()) {
        resultList.addToRear(((Integer) stack.pop()));
    }

    return (Iterator<T>) resultList.iterator();
}

Answer 1

From Cormen Introduction to algorithm. Dijkstra’s algorithm maintains a set S of vertices whose final shortest-path weights from the source s have already been determined. The algorithm repeatedly selects the vertex u 2 V S with the minimum shortest-path estimate, adds u to S, and relaxes all edges leaving u. In the following implementation, we use a min-priority queue Q of vertices, keyed by their d values.

DIJKSTRA.G;w; s/
1 INITIALIZE-SINGLE-SOURCE.G; s/
2 S D ;
3 Q D G:V
4 while Q ¤ ;
5 u D EXTRACT-MIN.Q/
6 S D S [ fug
7 for each vertex  2 G:AdjOEu
8 RELAX.u; ;w/DIJKSTRA.G;w; s/