-
Title:
Code for Dijkstra - Intro to Algorithms
-
Description:
-
So here's my attempt at translating that description of an algorithm
-
into actual Python code ended up using helpful structures
-
maybe a little different than before so I've got a Dijkstra's algorithm.
-
Dijkstra is the name of the individual who first described
-
and analyzed this algorithm for a single-source shortest path.
-
So we give it a single source. We give it a single node in the network.
-
Then we ask for the distance to all the other nodes in the network in graph G.
-
So the distance so far is a structure that's going to represent a mapping
-
from nodes to what we think the distance might be from V to that node.
-
And in our hand simulated algorithm, these are the numbers in the non-locked circles.
-
Some nodes might not have any numbers yet,
-
and the ones that have numbers are represented in that mapping.
-
So then we start structure off by saying well, the distance that we know of so far from V to the V,
-
the node that we started at, is zero, and we do that in the hand simulation as well.
-
Alright, now, there's an additional data structure, which I call final dist,
-
which is once we actually figured out what the real distance is,
-
we stick in this structure and so that's basically the numbers that are in the heavy circles here.
-
When a circle becomes heavy because I'm locking it down,
-
I moved that number into the final dist mapping, and I deleted it from the dist so far
-
so that number doesn't exist anymore in the dist so far mapping.
-
Now, we're going to iterate as long as the set of nodes
-
for which we've computed the distance is less than the total number of nodes.
-
Now, this is a little risky. I probably shouldn't have done this.
-
Because if the graph is disconnected, what this is going to do is this is how we're going to die.
-
Well, let's see where it's going to die, but it will keep trying to add nodes
-
in their final distances even though they aren't final distances to add.
-
So there's probably other test that might be better to determine
-
when everything that's reachable has actually been assigned value.
-
In general, this test isn't quite the right test, but it will suffice for a connected graph
-
and that's we're going to try it on.
-
What do we do as long as there's more nodes that we need to analyze,
-
Take the node that has the shortest distance of all the ones so far, call that w, and lock it down.
-
Locking it down in this case involves need printing a debugging message
-
saying that the final distance for w is whatever we computed the distance so far as.
-
We now know that this is the final distance and then we delete that from the dist so far structure.
-
Then we go through its neighbors.
-
All of the neighbors of w in the graphs called an x, and for each one, we'll say,
-
well, if we completely solved that neighbor then we don't have to do anything,
-
but if we haven't then see if it has a distance so far, and if it doesn't then give it one
-
by saying, well, our best guess is the distance.
-
It's going to be the distance that it took to get to w plus the distance from w to x.
-
On the other hand, if it already has the distance, check if the new distance,
-
the distance to w plus the distance from w to x, is better than the distance
-
that we had so far, and if it is, replace it.
-
This is sometimes called relaxation. It doesn't seem very relaxing but that's what it is.
-
And so now we've handled that node.
-
We handle all the nodes for the neighbors of w and that means we've handled w.
-
We've locked it down, and we can move on.
-
We go back up and handle the next node closest to the start state.
-
And once we've gone through all of the nodes and assigned them all their final distances
-
then we return that structure and we're done.
-
This is the Dijkstra's algorithm in a nutshell. Let's analyze this.