• Post Reply Bookmark Topic Watch Topic
  • New Topic

Dijkstra's Algorithm with Priority Queue  RSS feed

 
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello,
I was given some code by a professor to add some features to as part of an assignment. However, the code itself doesn't seem to work. I have tried contacting them but they are unresponsive, so until I can get in contact maybe someone can help me resolve why the code does not work.



The method to find minimum distance is nonfunctional...I receive an error that the types are incompatible. Can anyone help me get this working? I can't do the assignment if the base code doesn't work to begin with...
 
Ranch Hand
Posts: 30
Chrome Java Netbeans IDE
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
First, I thought that the standard was camel casing for better or worse as others on here have said.

But to the point on your problem, I would check what the remove method on priorityQueue returns. Perhaps it's returning type Node instead of int.
 
J Niewolak
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jarrod Rackley wrote:First, I thought that the standard was camel casing for better or worse as others on here have said.

But to the point on your problem, I would check what the remove method on priorityQueue returns. Perhaps it's returning type Node instead of int.


Apparently the return type is boolean, I had checked the documentation. I'm not sure how to modify the method to be correct though, or how involved that would be.
 
Jarrod Rackley
Ranch Hand
Posts: 30
Chrome Java Netbeans IDE
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Is the remove and overloaded method?
 
J Niewolak
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jarrod Rackley wrote:Is the remove and overloaded method?


I don't think so, this seems to be the full code. It was given by the teacher but it appears to be directly copied from here: http://www.sanfoundry.com/java-program-mplement-dijkstras-algorithm-using-priority_queue/
 
Jarrod Rackley
Ranch Hand
Posts: 30
Chrome Java Netbeans IDE
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Okay, after looking at it some more. You need to import Comparator, and priorityQueue.remove() is removing the head of the queue. It's going to return Type Node which is not compatible with int. The remove method can also throw an exception if the queue is empty. I would put it in a try/catch block just in case. But to get it to stop fussing about the int/node compatibility I would have it get the node attribute out of the node object, since that is an int.

 
Marshal
Posts: 56610
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch

You have some useful answers there
I agree with the comments about code style; that looks like code which somebody who is used to C had written. There are some formatting inconsistencies, e.g. mixing tabs and spaces for indenting, inconsistent insertion or omission of {} and the double‑spacing, which I got rid of, makes it harder to read. And the assertion on the link you posted that the code compiles and runs on a Linux box, is simply incorrect.
I can see three design errors:
  • 1: Closing a Scanner pointing to System.in
  • 2: Making the Node class implement Comparator rather than Comparable. Comparator is intended for a separate class to compare something else.
  • 3: (Possible error) No-arguments constructor in Node which allows a Node with both fields set to 0.

  • You cannot understand programs about algorithms until you understand the algorithm. So: what is Dijkstra's algorithm?

    [Edit]The inconsistent {} are on lines 27-33 in the version without double‑spacing[edit]
     
    Campbell Ritchie
    Marshal
    Posts: 56610
    172
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Suggested corrections:More formatting problems: the constant indent by 4 spaces at the beginning of every line makes it look as though Node were an inner class, but it is a top‑level class.
    The square brackets are part of the type so it should read
    int[] myArray
    not int myArray[]. The latter is correct in C, however.
     
    Campbell Ritchie
    Marshal
    Posts: 56610
    172
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    The code I posted with those corrections will both compile and run with the input on the sanfactory page.. There is no need to use a Comparator, so the additional import is unnecessary.
    It just goes to show how careful you have to be with code downloaded from the net, because there is so much rubbish available.
     
    Bartender
    Posts: 2087
    44
    Firefox Browser IntelliJ IDE Java Linux Spring
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Campbell Ritchie wrote:The square brackets are part of the type so it should read
    int[] myArray
    not int myArray[]. The latter is correct in C, however.

    Just as a note: The declaration int myArray[] is legal Java syntax.
    However, it should be avoided as Campbell suggested.
     
    Campbell Ritchie
    Marshal
    Posts: 56610
    172
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I meant that to be a formatting/style problem, but you are right to point out that it is permitted by the language, PP. Thank you.

    From the Java Tutorials:
    You can also place the brackets after the array's name:

    // this form is discouraged
    float anArrayOfFloats[];

    However, convention discourages this form; the brackets identify the array type and should appear with the type designation.
     
    Campbell Ritchie
    Marshal
    Posts: 56610
    172
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I made a mistake in the code I posted earlier; I wrote .node on line 46 when it should have read .getNode()
    Have corrected the post, changing node to getNode()
     
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!