• (2 Pages)
  • +
  • 1
  • 2

Data Structures: Dijkstra's Algorithm Rate Topic: ***** 1 Votes

#16 peterjdickson  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 24-June 11

Posted 27 June 2011 - 11:21 AM

Verbatim! In the main do/while loop, the heap is growing by 2 every pass. Is it possible that the code posted online has a defect? Could you post your sample code you are running as a compressed attachment? Thanks!
Was This Post Helpful? 0
  • +
  • -

#17 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10391
  • View blog
  • Posts: 38,455
  • Joined: 27-December 08

Posted 27 June 2011 - 11:38 AM

My code is on my home computer. I'll check later tonight and see what's going on. It's possible I accidentally posted an old version, but I'm pretty sure this is the most recent one.
Was This Post Helpful? 0
  • +
  • -

#18 peterjdickson  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 24-June 11

Posted 27 June 2011 - 12:07 PM

I'm fairly sure that the posted code doesn't have any support for detecting Vertexes (Connections) that have already been visited and it immediately get's into an inf-loop. I added support for marking Connections as having been visited and think I have a solution. I would be very interested in seeing yours to make sure I have optimized this. Thanks!
Was This Post Helpful? 0
  • +
  • -

#19 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10391
  • View blog
  • Posts: 38,455
  • Joined: 27-December 08

Posted 27 June 2011 - 02:24 PM

It looks like I made some changes to my Edge class in my Graphs tutorial for some other stuff I did. I updated it in my Graphs tutorial. Try again. You should be good to go. :)
Was This Post Helpful? 0
  • +
  • -

#20 kilroyreturns  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 23-November 11

Posted 23 November 2011 - 09:45 PM

Sorry to bring this post back to life, but been looking over the code for a bit and been trying to figure this out. Is there any way for the program to return the path that was taken to the shortest root? For example if the command was

 test.heapPath(i, n);


to output: i,k.n = 11

Thank you for your help, and sorry
Was This Post Helpful? 0
  • +
  • -

#21 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10391
  • View blog
  • Posts: 38,455
  • Joined: 27-December 08

Posted 01 December 2011 - 07:53 PM

You could have an array of size V. Obviously the starting and ending points would be the first and last elements. But once you find the closest Vertex from the starting point, you would update the appropriate position in the array. Follow along this train of logic for each individual Vertex.
Was This Post Helpful? 0
  • +
  • -

#22 afsa  Icon User is offline

  • New D.I.C Head

Reputation: -1
  • View blog
  • Posts: 1
  • Joined: 30-August 10

Posted 28 July 2013 - 01:36 AM

Can You please share complete code of Dijkestra's Algorithm with me..

This post has been edited by macosxnerd101: 02 August 2013 - 11:21 AM
Reason for edit:: Removed quote

Was This Post Helpful? -1
  • +
  • -

#23 chris76  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 25-March 14

Posted 25 March 2014 - 01:30 PM

This program calculates the shortest distance. How to find the shortest path ? any help is appreciated.


View Postpeterjdickson, on 24 June 2011 - 06:11 PM, said:

Hello, I loaded up your sample classes (verbatim) and attempted to execute the heapPath solution to your Wiki sample graph.

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.util.Arrays.copyOf(Arrays.java:2760)
at java.util.Arrays.copyOf(Arrays.java:2734)
at java.util.PriorityQueue.grow(PriorityQueue.java:238)
at java.util.PriorityQueue.offer(PriorityQueue.java:269)
at java.util.PriorityQueue.add(PriorityQueue.java:251)
at dijkstra.Dijkstra.heapPath(Dijkstra.java:112)
at dijkstra.Main.main(Main.java:43)

Any suggestions? Thanks! I can post my test of your sample if you would like!

Was This Post Helpful? 0
  • +
  • -

#24 chris76  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 25-March 14

Posted 25 March 2014 - 01:42 PM

The heapPath method returns the shortest distance. How to get shortest path ? Please help.
Was This Post Helpful? 0
  • +
  • -

#25 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 8940
  • View blog
  • Posts: 33,526
  • Joined: 12-June 08

Posted 25 March 2014 - 01:43 PM

I think one post on this is sufficient - let's not spam the thread with your repeated question.

Thanks.
Was This Post Helpful? 0
  • +
  • -

#26 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10391
  • View blog
  • Posts: 38,455
  • Joined: 27-December 08

Posted 25 March 2014 - 02:53 PM

To get the shortest paths, essentially you'd be growing a tree. When you add an edge that creates a cycle, you remove the edge present before the cycle. So if I go from a-b and a-c, then b-c, I have a cycle. If a-b-c is shorter than a-c, I remove the a-c edge. Otherwise, I keep the a-c edge and discard the b-c edge.

The resulting tree will give you the shortest paths from your starting point to each vertex in the graph.
Was This Post Helpful? 0
  • +
  • -

#27 chris76  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 25-March 14

Posted 25 March 2014 - 03:40 PM

thanks for the quick response.

In the heapPath method, i tried to get the elements that are visited.. But it is giving all the nodes that was visited but not the shortest path. I haven't specifically called the remove method in heap
if (newDist < distance) {
					evaluate.setDistance(newDist);
					if(heap.peek().getDistance() < currentfuel) {
						rootArray.add(hm.get(evaluate.getElem()));
					}
					System.out.println("final dist is: "+ evaluate.getDistance());
					System.out.println();
				}


Can you help me add the required code for finding shortest path or send me your entire heapPath method ?

Thanks a lot.

This post has been edited by macosxnerd101: 25 March 2014 - 03:48 PM
Reason for edit:: Please use code tags

Was This Post Helpful? 0
  • +
  • -

#28 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10391
  • View blog
  • Posts: 38,455
  • Joined: 27-December 08

Posted 25 March 2014 - 03:52 PM

Quote

Can you help me add the required code for finding shortest path or send me your entire heapPath method ?

I'm not in the business of handing people homework solutions. I honestly haven't touched this code in a few years, so my entire heapPath() method is what is posted.

I will say this- Dijkstra's algorithm works because of an exchange argument I outlined in my previous post. You need to swap out edges in your update. So if the a-b-c path is shorter than the a-c path, you need to remove the edge a-c. You are not handling this removal.
Was This Post Helpful? 0
  • +
  • -

#29 chris76  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 25-March 14

Posted 25 March 2014 - 04:09 PM

Thanks for the help.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2