Win a copy of High Performance Python for Data Analytics this week in the Python forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
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
Chrome Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 ..


I desperately need your help.
Thanks in advance.
 
Bartender
Posts: 1845
10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Chrome Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks for the reply!

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
    Python C++ Linux
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Is this for the Stanford algorithms class? If not, sign up and skip to the lecture on this.
     
    Alicia Perry
    Ranch Hand
    Posts: 66
    Chrome Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    What is Stanford algorithm?
     
    Marshal
    Posts: 71772
    312
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Stanford is a university. They make many of their courses available free of charge on the net.
     
    Stefan Evans
    Bartender
    Posts: 1845
    10
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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
    Chrome Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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
    Chrome Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    I read pseudocode on Wikipedia.
    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
    Chrome Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Someone help me? I don't know how to go forward..
    Thanks
     
    Bartender
    Posts: 4272
    160
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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
    Chrome Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Thanks Piet, I've solved!
     
    Campbell Ritchie
    Marshal
    Posts: 71772
    312
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Well done both of you
     
    Piet Souris
    Bartender
    Posts: 4272
    160
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    @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
     
    reply
      Bookmark Topic Watch Topic
    • New Topic