hi Alicia,
just reading this topic, and I just implemented the Graph interface,
to
test out how I would implement it. But I have not tested it yet.
Nor have I implemented the shortest path method.
It is remarkable that some topics get drowned in the replies, where
a dozen or so repliers keep replying, while some other topics hardly
get any attention. I've seen this happening here, so this site would
be a good source of investigation for a graduate in sociology.
What I can do for now is to offer a simpler version, not exactly Dijkstra
but sort of, that I used to solve one of Project Euler's exercizes.
There we were given an 80 by 80 matrix, with numbers in each cell, and
the question was to find that path from [0,0] to [79,79] that
had the smallest sum. Standing in a cell, you could move in all four directions
to a neighboring cell. Sounds a lot like your problem, doesn't it?
Instead of four neighboring cells, we have an adjacency list for a vertex,
and instead of a number in a cell we have the weight of an edge.
The algorithm I used was:
* I have a class 'Veld', containing the members: "int pathLengthSoFar" and
"Veld previousVeld". Read 'Vertex' for 'Veld'
* and I have a LinkedList<Veld>, that serves as my queue, I do
not use any Priority Que, and here I diverge from Dijkstra. But I leave it
up to you whether this is important or not.
Starting from the given Vertex_Begin,with pathLengthSoFar = 0 and previousVertex
= null, I put it at the back of the empty LL.
Then, while the LL is not empty:
* retrieve the first element V of the LL
* get all the adjacents of V
* for each adjacent A, see if V.currentValue + weight(V,A) (call it sum) < A.currentValue.
* If so, change A.currentValue to sum, set A.previousVertex to V, and put A back in the LL, at the end!
* otherwise, no action needed.
* and repeat, until the LL is empty.
* after that, start at the target vertex, and follow the links of the previousVertex, all the way back
to Vertex_Begin. Of course, there may not be a path from begin to taget, so the target may not be
present in the list of all the special vertices.
This is the routine I used:
(note: bord[][] is a two dimensional matrix of Veld)
Tomorrow I will have a closer look at your code. Did you test your code?
If so, what were your findings? Did you get a full Graph<V, E> implementation?
Greetz,
Piet