|
Question 211981: How does Dijkstras Algorithm work? Ive looked up some sites and my teacher recommends http://www.deakin.edu.au/~agoodman/graph/dijkstra2.htm that one but it makes no sense, whats a simple way to do it?
Answer by Theo(13342)   (Show Source):
You can put this solution on YOUR website! try this one
-----
http://www.animal.ahrgr.de/showAnimationDetails.php3?lang=en&anim=15
-----
my take:
He's trying to find the shortest path from A to F.
to any other node in the network.
-----
He looks at the direct paths available from node A.
That is to nodes C, E, D, and B.
-----
He constructs a table showing the distance between them. The distance can be weighted by anything you want it to be. Length, Cost, Bandwidth, etc. Whatever feature you prefer over another one you assign it the least cost. If distance is your measure, then the least cost is based on distance with the shortest distance costing the least, etc.
-----
On his first pass he constructs a table listing the nodes that were visited and the cost to get to each.
As you can see, his costs are listed between each node on the line between them.
-----
He creates his first list and then looks to see if there are other paths that are cheaper.
He finds a cheaper path from A to E by going through C. A to E direct costs 4. A to C to E costs 3. He updates his table showing that the cheapest path from A to E is A to C to E.
-----
He then looks to go to an unvisited node. On his second pass he adds node F. Nothing's really changed except the addition of node F. All other costs have remained the same because he hasn't found a cheaper route to any of them yet.
You see the cost to get to node F is 8. That would be node A to B to F which has a total cost of 8. Not sure why he chose that next, but maybe because it was the smallest number of links to get there.
-----
On his 3d pass looks like he found a cheaper path to get from A to D because the cost changed from 6 to 5. Looking at the map you can see the original path was probably A to D direct. Looks like he found a cheaper path by going from A to E to D because the cost of that is 5. Looks like he also found a cheaper path from A to F. His original path was A to B to F costing 8. His new found path is A to C to D to F which costs 7.
-----
On his 4th pass he found a cheaper path to F again. This time he went from A to C to E to D to F which costs 6 (2+1+2+1)
-----
Looks like he starts out looking for new nodes on a direct path from the node he's on. Once he's reached all the nodes he can reach he then looks to see if there are cheaper paths to those nodes. If he finds them he updates his table. When he's satisfied he can't find any cheaper paths to the existing nodes, he starts from the edges of the network and looks to find more new nodes on direct paths. Once he's found all he can find, he then looks to see if there are cheaper paths to those nodes. He continues until he can't find any cheaper paths. He continues this until all nodes are covered.
-----
at least that's what i think he's doing.
-----
| |
|
| |
