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();
}
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.