Dijkstra's algorithm

[Alicia Perry]

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:

public List<V> minPath(Graph<V, E> graph, V source, V dest) {
   ...
}

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 ..

public List<V> minPath(Graph<V, E> graph, V source, V dest) {
    List<V> list = new ArrayList<V>();
    if(!graph.hasVertex(source) || !graph.hasVertex(dest))
      list = null;
    return list;
}

I desperately need your help.
Thanks in advance.

[Stefan Evans]

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]

Thanks for the reply!

The pseudocode is:

minPaths(Graph G from Node source s) { 
	foreach(Node x of G) { 
		dist[x] = ∞; 
		dad[x] = -1; 
	} 
	dad[s] = s; 
	dist[s] = 0; 
	Q = PriorityQueue_Empty; 
	foreach(Nodo x of G) 
		add x with priority dist[x] in Q; 
	while(Q is not empty) { 
		u = extract from Q the node with min dist; 
		foreach(Node v near u) { 
			if(dist[u] + c_uv < dist[v]) { 
				dad[v] = u; 
				dist[v] = dist[u] + c_uv; 
				decreasePriority(v, dist[v], Q); 
			} 
		} 
	} 
}

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?

[Guillermo Ishi]

Is this for the Stanford algorithms class? If not, sign up and skip to the lecture on this.

[Alicia Perry]

What is Stanford algorithm?

[Campbell Ritchie]

Stanford is a university. They make many of their courses available free of charge on the net.

[Stefan Evans]

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]

Hi, methods in class Graph are those in this interface....

public interface Graph<V, E> {
  
  boolean addVertex(V vertex);

  boolean addEdge(V vertex1, V vertex2, E data);

  boolean hasVertex(V vertex);

  boolean hasEdge(V vertex1, V vertex2);

  E getData(V vertex1, V vertex2);

  Collection<V> getVertices();

  Collection<V> getNeighbors(V vertex);
  
}

SparseGraph class implements the methods using a HashMap:

public class SparseGraph<V, E> implements Graph<V, E> {
  
  public HashMap<V, HashMap<V, E>> map = new HashMap<V, HashMap<V, E>>();
  
  ...
  
}

I'm reading the pseudocode on wikipedia..

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

  public List<V> minPath(Graph<V, E> graph, V source, V dest) {
    List<V> list = new ArrayList<V>();
    
    HashMap<V, Integer> prev = new HashMap<V, Integer>();
    
    int[] dist;
    int i = 0;
    
    Collection<V> vertices = graph.getVertices();
    Iterator iterator = vertices.iterator();
    
    while(iterator.hasNext()) { //foreach(vertex in graph)
      //dist[vertex] = Double.POSITIVE_INFINITY;
      //prev[vertex] = -1;
    }
    
    //dist[source] = 0;
    //prev[source] = source;
    
    ...

    return list;
  }

[Alicia Perry]

I read pseudocode on Wikipedia.
This is the algorithm that I wrote.. It might be correct? I think that the line 26 is wrong ..

  public List<V> minPath(Graph<V, E> graph, V source, V dest) {
    List<V> list = new ArrayList<V>();
    ArrayList<V> vertices = (ArrayList<V>) graph.getVertices();
    
    PriorityQueueHeap<V, Double> q = new PriorityQueueHeap<V, Double>(vertices.size());
    
    HashMap<V, V> prev = new HashMap<V, V>();
    HashMap<V, Double> dist = new HashMap<V, Double>();
    
    for(V v : vertices) {
      dist.put(v, Double.POSITIVE_INFINITY); 
      prev.put(v, null); 
    }
    prev.put(source, source); 
    dist.put(source, 0.0); 
    
    for(V v : vertices) { 
      q.add(v, dist.get(v)); 
    }
    
    while(!q.isEmpty()) { 
      V u = dest;
      while(prev.get(u) != null) {
        list.add(u);
        u = (V) prev.get(u);
      }
    }
    return list;
  }

Thanks!

[Alicia Perry]

Someone help me? I don't know how to go forward..
Thanks

[Piet Souris]

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)

bord[0][0].currentValue = bord[0][0].originalValue;
      queue.addLast(bord[0][0]);
      
      while (!queue.isEmpty()) {
         Veld Q = queue.pollFirst();
//         a("just popped from the queuet: " + Q.toString());
         List<Veld> neighbors = getNeighbors(Q);
         for (Veld v : neighbors) {
            if ((v.currentValue == -1)  ||
                (v.originalValue + Q.currentValue < v.currentValue)
            ) {
               v.currentValue = v.originalValue + Q.currentValue;
               // instead of the next two lines, you would have: v.previousVertex = Q;
               v.x_voor = Q.x;
               v.y_voor = Q.y;
               queue.addLast(v);
            }
         }
         System.out.println("lengte queue: " + queue.size());
      }

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]

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]

Thanks Piet, I've solved!

[Campbell Ritchie]

Well done both of you

[Piet Souris]

@Campbell
Thank you!

@Alicia
Glad I could help.
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)
was not found when I only had inserted edge(0,2).
That was due to how I had defined the hashCode.

Now, I knew about this matter, but had actually never
encountered it in practise.
I found this to be so illustrative, that I would advise
you give it a try too)

Greetz,
Piet