Win a copy of High Performance Python for Data Analytics this week in the Python forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Paul Clapham
• Ron McLeod
• Bear Bibeault
• Liutauras Vilda
Sheriffs:
• Jeanne Boyarsky
• Tim Cooke
• Junilu Lacar
Saloon Keepers:
• Tim Moores
• Tim Holloway
• Stephan van Hulst
• Jj Roberts
• Carey Brown
Bartenders:
• salvin francis
• Frits Walraven
• Piet Souris

# Dijkstra's algorithm

Ranch Hand
Posts: 66
• Number of slices to send:
Optional 'thank-you' note:
Hello everyone, I am studying Dijkstra's algorithm and I think I understand it but I'm distressed when I have to implement it.
I created a class SparseGraph representing directed graphs weighed.
Now I have to complete this required method:

This method returns the list of the vertices on the shortest path between a source 'source' and a destination 'dest'.
The algorithm returns the empty list if there is a path between 'source' and 'dest'.

How can I do? for now I only wrote these two lines .. I don't know how to go forward ..

Bartender
Posts: 1845
10
• Number of slices to send:
Optional 'thank-you' note:
What information do you need to keep track of to perform Dijkstra's algorithm?
How are you proposing to remember this information? You probably need a list of 'unvisited' vertices at the least.

You can get a list of edges and their costs from a vertex?
That would be a starting point.

Alicia Perry
Ranch Hand
Posts: 66
• Number of slices to send:
Optional 'thank-you' note:

The pseudocode is:

So I need:
• a priority queue of type V
• an array (what kind? an array or other data structure is better?) distances
• an array (what kind? an array or other data structure is better?) of the fathers, useful to build the tree of visit

• I'm right?

Ranch Hand
Posts: 789
• Number of slices to send:
Optional 'thank-you' note:

Alicia Perry
Ranch Hand
Posts: 66
• Number of slices to send:
Optional 'thank-you' note:
What is Stanford algorithm?

Marshal
Posts: 71772
312
• Number of slices to send:
Optional 'thank-you' note:
Stanford is a university. They make many of their courses available free of charge on the net.

Stefan Evans
Bartender
Posts: 1845
10
• Number of slices to send:
Optional 'thank-you' note:
I'm not sure copying that pseudo code is going to help you much. It doesn't have it's variables named very well, and there are items like 'decreasePriority' which doesn't have much explanation.
I find the pseudocode at Dijkstra's algorithm on wikipedia to be clearer

A priority queue isn't absolutely necessary. Using one just makes it easy to find the 'next node' you should look at.

There are probably some useful methods on the Graph class to help you out.

In terms of data structures, I would probably use a Map<V, Integer> - mapping a graph vertex (V) to a number representing how far it is to that node.
But I don't know if you have learned about Maps yet.

What things can you do with a Graph? What methods are available on it? I presume that given a Vertex, you can get its edges? Write some code doing that.

Alicia Perry
Ranch Hand
Posts: 66
• Number of slices to send:
Optional 'thank-you' note:
Hi, methods in class Graph are those in this interface....

SparseGraph class implements the methods using a HashMap:

I'm reading the pseudocode on wikipedia..

I tried to write this code, but it's absolutely wrong..

Alicia Perry
Ranch Hand
Posts: 66
• Number of slices to send:
Optional 'thank-you' note:
This is the algorithm that I wrote.. It might be correct? I think that the line 26 is wrong ..

Thanks!

Alicia Perry
Ranch Hand
Posts: 66
• Number of slices to send:
Optional 'thank-you' note:
Someone help me? I don't know how to go forward..
Thanks

Bartender
Posts: 4272
160
• Number of slices to send:
Optional 'thank-you' note:
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

Piet Souris
Bartender
Posts: 4272
160
• Number of slices to send:
Optional 'thank-you' note:
hi Alicia,

just a quick question:

in your construction, where are your weights coming from? I assumed that <E>
served for that purpose, but that is just a guess.

If E is indeed used for that purpose (because if you look at the method
'addEdge' you see that it is data that comes with an edge).
If so, then it is hard to see how to get a generic shortestPath
method, since there is no generic way to add 'E's together..

The PriorityQueue seems oke.

Greetz,
Piet

Alicia Perry
Ranch Hand
Posts: 66
• Number of slices to send:
Optional 'thank-you' note:
Thanks Piet, I've solved!

Campbell Ritchie
Marshal
Posts: 71772
312
• Number of slices to send:
Optional 'thank-you' note:
Well done both of you

Piet Souris
Bartender
Posts: 4272
160
• Number of slices to send:
Optional 'thank-you' note:
@Campbell
Thank you!

@Alicia
I implemented the shortestPath such that I use <E> if E
is a (subclass of) Number, or else I assume each edge to have
a weight of 1. How did you handle this?

(By the way: I also added, to the interface, the method:

boolean isDirected()

and that has some very interesting consequences with
respect to equals and hashCode. For instance, at first
I had it such that edge(0, 2) was equal to edge(2,0) in
an undirected graph, but that nevertheless edge(2,0)