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 ...
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Bear Bibeault
  • Liutauras Vilda
  • Jeanne Boyarsky
  • Tim Cooke
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Stephan van Hulst
  • Jj Roberts
  • Carey Brown
  • salvin francis
  • Frits Walraven
  • Piet Souris

Dijkstras Algorithm

Posts: 8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I came across an interesting programming challenge, which I'm trying to solve.

In my mind Dijkstras algorithm is the best solution, since what they're essentially asking is to find the shortest path in a un-directed graph.

Here is my solution, but I don't get the correct answer, so I'd like some feedback on my code. Maybe my mistake is obvious.

Any help on the would truly be appreciated!

Posts: 1845
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Feedback on code: It is fairly hard to read.
Some more comments and better variable names might help a little.

I could follow the reading in of input. The Junctions and Paths are explained in the problem definition. What are "vertices" ?
But then I got lost at line 42 when you are in loop doing calculations:

That line looks funny to me.
Getting a junction by index based on the x value of a path!?!?
What is this loop trying to accomplish?
What do the x,y, x1,y1 represent?

Suggestions for debugging:
Add logging statements at various points to check what is happening in your internal program.

This bit also looks wrong to me.

I assume "h" and "v" are the total distance travelled horizontally and vertically within the path.
I am pretty sure you should not be using h and v (distance travelled so far) in the Math.abs calculation. You should be looking at current and previous junctions to determine how much to add to h and v travelled to date.

Also rather than typing in the numbers each time, try the following:

It saves MASSIVE amounts of time running it if you don't have to type in the details again each time.
You should try refactoring your code to allow that a bit easier.
Posts: 16061
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
As far as readability, I didn't find it too bad. Some variable names could be more explicit to differentiate them from others. For example, some parts use v to refer to a vertex while other parts use v to refer to a vertical distance. Having to differentiate between h and H also adds to the conceptual weight. The static method readInput in the Coordinate class is really a static factory method so it's better to name it something like newCoordinateFrom or something like that. Names are better when they reveal the logical intent rather than the technical details.

I referred to the problem that you linked to and you seem to have pretty much followed the names used there but it's still a bit of a bother to flip back and forth to see what some variables are supposed to represent.

It would help if you told us which particular variation of the algorithm you are trying to implement just so we are on the same page. If you have some pseudo code that you based your implementation, please share it.

Also, from the problem:

Now he has thoughts about returning the vehicle back to the seller. But he first wants to know, if it's even worth it. That's why he wants to know the number of unordered pairs (i,j) such that it is not possible to drive a customer from junction i to junction j.

Are you sure your results represent these or are you getting the shortest paths? Because I don't think you're actually looking for the shortest paths as the solution here. I don't know, I could be wrong but that's what it seems to me after a cursory read.
Consider Paul's rocket mass heater.
    Bookmark Topic Watch Topic
  • New Topic