What we have here is a Python encoding of the breadth-first search algorithm
we've been talking about for finding shortest paths in these kind of graphs.
In this particular case, there are some infrastructure in the beginning for reading the data
for the comic book characters from a file.
The one that we're using here is tens of thousands of lines long.
So, it would be very awkward to put it directly into Python.
A pretty simple code, we're just going to reading it and then making links into graph G.
That graph is stored as marvelG.
That's the graph of the comic book characters and the comic books.
Then, we've got a subroutine called path (G, V₁,V₂) and what that does is it takes graph G, a start node,
let's say a character in the comic book and an ending node in another character in the comic book
and it tries t find the shortest path between them.
In fact, it will, unless there isn't one.
So, in this particular case, the code here is only going to tell us the length of the shortest path.
It turns out that's a pretty straight forward thing to do, but it's not that hard to augment this
to actually produce the path itself but let's just start of with the--the length.
So, we create a data structure distance from the start
which is going to map the nodes of the graph to how far away they are from (V₁).
We have an open_list, just like we've been taking about and it's initialized to just the very first node,
and the distance from the start from that node is zero because it is the node itself.
Now, we're going to proceed by checking to see whether the open_list is empty.
If it's not, then we go into loop here that says--
first we're going to pull off the very beginning element of the open_list, and call that current.
And then we're going to delete the very first element to the open_list, so that it's gone.
We are going to talk a little bit later about how to try to make this operation as efficient as possible.
But for now, this is--this is okay.
It's going to be fast enough, so it takes that off the open list and now what we're supposed to do,
we loop through the neighbors, so here we have a statement that says,
for each neighbor in the list of neighbors (current),
What is it going to do? It's going to check to see
whether or not that neighbor's been assigned the distance so far.
If it has not been assigned a distance, is because it's not been visited. It's not been marked.
And if that's the case, then what we're going to do is we're going to
calculate the distance from the start for that node or what is it going to be?
The neighbor--the one--the node--the new node that we just discovered
is just one step farther from the start than the node that we're expanding.
So, we take the distance from the start to where we are now.
Add one to it and that's the start to this neighbor that we're considering.
So this is really the key step. It is finding the distance of the shortest path.
Once that distance has been assigned, we check
"Hey, was that the neighbor the one we're actually searching for?" If it is, we can just be done.
We can just return that distance for that node;
otherwise, we have to proceed and we take that neighbor
and we just stick it on the end bar open_list, so that we'll catch up with it later.
And then we're back into the loop and it's just going to continue pulling things off the open list.
assigning the distances until finally we discover the node they were looking for,
or if the open list eventually goes completely empty.
All this falls all the way through the while loop is done
and it returns false, so instead of actually returning a distance, it's going to return false meaning
I wasn't able to find a path.
This could also be infinity which indicates that there is no bound on the length
of the shortest path--it's infinitely large.
This particular case I'm running it with finding the path
from a comic book character called A to one called ZZZAX.
I figured that was pretty comprehensive if we go from A to ZZZAX.
And it's had three or four step chain that you get when you do this with the data that we've got.
All right, so let's go through the changes we need to make
to actually return the path instead of the distance.
What I'm going to do is actually ??? this variable distance from the start.
It's not going to be a distance anymore.
It's actually going to be the path, so instead of it starting at zero,
it starts as just a list consisting of (V₁) by itself and the only other change that we need to do is
when we extend it because we've discovered a path from the beginning through a current,
now goes to neighbor, all we need to do is that.
It says, this--this now being a list, when we add another list to it,
it's just depending to the--to the end of it, which is what we want in this case.
It might not be the most efficient way to do it but
things don't get very large, and it actually works pretty well.