?
Solved

Dijkstra's Algorithm

Posted on 2005-03-21
2
Medium Priority
?
1,353 Views
Last Modified: 2010-10-05
So Dijkstra's algorithm returns the least total weight to each vertex from a starting vertex. How do I get the path it took to get from one vertex to another? None of the visitor's I've tried do what I need.
0
Comment
Question by:bradtm
2 Comments
 
LVL 10

Accepted Solution

by:
Andrew Beers earned 1000 total points
ID: 13600934
"So Dijkstra's algorithm returns the least total weight to each vertex from a starting vertex. How do I get the path it took to get from one vertex to another? None of the visitor's I've tried do what I need."

Dijkstra's algorithm finds the shortest path from one vetex to another with the shortest total cost (the sum of each paths value) or it can be refered to as weight.  You want to track which path you took?!

Use a linked list.  Easy implimentation... trace your steps.  A decent example of how to impliment this is here:

http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml

The main idea is to plug in one vertex and then have a value of the weight of the line and then go to the next.  If you must back-track you just unplug nodes as far back as you want (Using the same algorithm as you do in your math classes.  Just put it into programming... that example is in Java.  If you want a different example just ask).

I think that was your question but your question wasn't very specific.  Please specify further if your question is not answered thus far.

~Aqua
0
 
LVL 31

Assisted Solution

by:GwynforWeb
GwynforWeb earned 1000 total points
ID: 13703583
Dijkstra's algoritm in its pure form does not find the shortest path from a starting node to all others it finds the shortest distances. To find the shortest paths you modify the algorithm to grow a tree of shorstest paths from the staring node. A new node is added to the tree as its shortest distance is discovered and the node is added to the tree with its parent being the node that added it. You store the tree as a parent sibling table.
0

Featured Post

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

As game developers, we quickly learn that Artificial Intelligence (AI) doesn’t need to be so tough.  To reference Space Ghost: “Moltar, I have a giant brain that is able to reduce any complex machine into a simple yes or no answer. (http://www.youtu…
Recently, in one of the tech-blogs I usually read, I saw a post about the best-selling video games through history. The first place in the list is for the classic, extremely addictive Tetris. Well, a long time ago, in a galaxy far far away, I was…
The Relationships Diagram is a good way to get an overall view of what a database is keeping track of. It is also where relationships are defined. A relationship specifies how two tables connect to each other. As you build tables in Microsoft Ac…
Stellar Phoenix SQL Database Repair software easily fixes the suspect mode issue of SQL Server database. It is a simple process to bring the database from suspect mode to normal mode. Check out the video and fix the SQL database suspect mode problem.
Suggested Courses

621 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question