?
Solved

Dijkstra's Algorithm

Posted on 2005-03-21
2
Medium Priority
?
1,348 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
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

Will your db performance match your db growth?

In Percona’s white paper “Performance at Scale: Keeping Your Database on Its Toes,” we take a high-level approach to what you need to think about when planning for database scalability.

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…
Performance in games development is paramount: every microsecond counts to be able to do everything in less than 33ms (aiming at 16ms). C# foreach statement is one of the worst performance killers, and here I explain why.
Michael from AdRem Software outlines event notifications and Automatic Corrective Actions in network monitoring. Automatic Corrective Actions are scripts, which can automatically run upon discovery of a certain undesirable condition in your network.…
In this video, Percona Solution Engineer Rick Golba discuss how (and why) you implement high availability in a database environment. To discuss how Percona Consulting can help with your design and architecture needs for your database and infrastr…

770 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