Dijkstra's algorithm finds the shortest path from a given starting node to all of the other nodes in the graph. It requires that the weights of all edges are non-negative. It operates by maintaining a set of "visited" nodes and continually updating the tentative distance to all of the unvisited nodes. At each iteration, the closest unvisited node is added to the visited set and the distances to its unvisited neighbors are updated.
"We start by drawing up a list of all the islands in the entire city G'Raph." began Edgar. "We say that they are all 'unvisited' and have a tentative distance of infinity. Except the starting island itself; we give that a distance of zero. You can always get from here to here without moving."
"But distances of infinity are obviously not correct." interrupted Ann. She had walked from the inn to the library this morning, and it had not been an infinite distance.
"Of course it isn't correct." agreed Florence. "Dijkstra's algorithm keeps finding SHORTER paths to each node. So the distance will keep going down as we update our list. But since we have not found any paths at this point, we use the largest distance that we can. That way, any path we find will be better."
That explanation sounded reasonable to Ann. However, she did not quite see where this was going.
"Then the fun begins." continued Edgar. "We keep visiting islands until we have visited them all! This is the part where we get to drive around on scooters."
He took a deep breath before launching into the explanation.
"Each time we finish visiting a new island, we follow the same procedure:
1) We find the unvisited island that has the closest distance to our starting point.
2) We go to the island on our scooters. Usually, Florence and I like to race. That adds some more excitement.
3) We find all of the islands connected to the one we are on -- all of its neighbors -- and update their tentative distances. For each unvisited neighbor, we compute how far it is from the starting island IF we go through the current island. That is: the distance to the current island plus the distance to its neighbor. If this new distance is shorter, then that becomes the island's new tentative distance.
4) We mark the current island as visited, knowing that we now have the shortest path to that island.
Then we just repeat the procedure for the next closest unvisited island." described Edgar.
"And at the end, all of the islands have been visited, and we have a list of the shortest distances to each one." added Florence.
Ann looked at them blankly. "But I don't understand…" she started.
"An example will help." exclaimed Edgar. "Let's say that we start at the library. That becomes our current node -- with distance zero. Everything else starts with an infinite distance."
"Then we look at the neighbors and update their tentative distances." he continued. "In this case the inn is at most 5 meters away and city hall is at most 18 meters away."
"Now we are done with the library's node. So we mark it as 'visited' and move to the next closest island -- the inn." he continued. "In this case it is a quick scooter drive and not much of a race. But it will get more exciting."
"Since the inn is the closest unvisited island, we know we have found the shortest path to it. So we can update both its distance and its path." he continued.
"Yay!" added Florence quietly from the side.
Edgar gave her a strange look. "Anyway... We do the same thing here. Updating the neighbor's distances. The inn has three neighboring islands to consider: the library (which is already visited), the dry cleaners, and the brewery."
"Then we again move onto the closest unvisited node. This time it is the brewery." Edgar explained. "We repeat the process there, updating the neighbors."
"Then onto city hall. Here is where things get very interesting. It is a good race from brewery to city hall." Edgar made driving motions with his hands as he explained this. "Also, on the algorithmic side, the distance from the library to the dry cleaners is shorter if we go past the inn instead past city hall. So we do NOT update the distance to the dry cleaners in this case, because we have already found a shorter path."
"Then onto the dry cleaners. And so forth." he concluded with a wave of his hand.
"Yes." agreed Ann. "I understand that part. You are expanding the set of visited nodes, and you are maintaining tentative distances to nodes along the unvisited frontier. Each time you find a shorter path to a node, you update its distance. But what I do not understand is…"
"Exactly! You are quick." proclaimed Edgar. "I bet that you are confused by the question of whether there could be a shorter path through other unvisited notes."
"No. I am not." declared Ann. "There cannot be a shorter path, because you are taking the CLOSEST unvisited node. If there was a shorter path, then you would have to go through another node. But we already know that that other node is further away, because it is not the CLOSEST. It would be like saying that it is 200 miles to Athens and 100 miles to Atlantis, but the shortest path to Atlantis is through Athens. It would not make any sense. What I am confused about is…"
"Why we add the distances?" ventured Edgar. "Well, that is simple. The distance of going from A to B through node C is the distance from A to C plus the distance from B to C."
By now Ann was aggravated at the interruptions. "No! I have walked before. I know that when you walk over two bridges the total distances is the sum of the bridges."
Ann continued before she could be interrupted again. "I understand the algorithm. It is all very clear. What I want to know is: Why do you have to use scooters? You already have all the distances between islands written on this map. You could do all of this without traveling to the islands physically."
Now Edgar looked at Ann blankly. "Why would we do that?"
Ann sighed. "Because it is a lot faster to just mark nodes on a map as 'visited' instead of actually visiting them. You could do this entire algorithm on paper without leaving the library."
Edgar looked at Florence for help. "But, scooters are the best part. What fun would it be without scooters?"
Florence agreed. "That is why we call them 'visited' nodes, because we get to visit them. That is the whole point."
"All I am saying is that you do not need to physically drive there if you already have a representation of the graph." Ann noted.
"I don't think you really understand the concepts yet." ventured Edgar. "Let me start again. Dijkstra's algorithm finds the shortest distance from any starting node to all other nodes in the graph…"
Ann sighed and sat quietly in the corner. As Edgar and Florence re-explained how to add unvisited neighbors to the visited list, Ann started to daydream about racing through G'Raph on a scooter. There was something odd appealing about that approach.
To be continued in Part 5: A Disagreement over Data Structures...
Follow Ann's visit to G'Raph from the beginning with Part 1: The City of G'Raph.
--------------
Also, check out the new illustrations added to the following stories:
- Arrays, Linked Lists, and Zed's Coffee Shop
- Why Tailors Use Insertion Sort
- Swapping Array Values and the Swimmy Friends Pet Store
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.