Original subtitles

In the previous section, we looked at planning problems on grids and

concluded that we could apply a grass fire algorithm or breadth-first search to

the resulting graph to find the shortest path between start node and a goal node.

Turns out that a similar algorithm can actually be applied to find the shortest

path to arbitrary graphs with non negative edge weights.

Let's consider the problem where we want to go from one town or village to another.

We modeled this problem with a graph.

With nodes correspond to the villages and

the edges correspond to the roadways between them.

We associate a number with each of the edges in the graph

to indicate the distance associated with each of those roads.

For concrete let's think of these distances as miles.

In other words,

our goal is to find the shortest path from node A to node E through the graph.

Or in other words, our goal is to find a path for

the start node to the end node that minimizes the sum of the weights or

costs associated with the edges along that path.

We begin by marking our starting node with a distance value of zero.

Here we use a red color to indicate that this node has been visited or marked.

We then mark each of the nodes that are adjacent to node A, in this case,

nodes B, D, and F.

We use the blue color to indicate that these notes are now

part of a list that we're currently considering.

Notice that we've associated a number with each of these nodes.

For instance, D now has a value of two, indicating that that's the shortest path

that we currently know about from the start node to that node D.

On the next iteration, we end up visiting node B

because that has the shortest associated distance of all of the blue nodes.

In visiting all of these neighbors,

we discover our route node C, which is of length 8,

indicating that this is currently the shortest path that we know of to C.

On the following iteration, we visit node D.

When we visit all the neighbors of D,

we notice that there is now a shorter path to node C, via node D, and

we update the distance associated with node C to five, to reflect this fact.

On the following iteration, we add node F And in visiting

each of its neighbors, we discover a shorter path to node G, as shown here.

Next iteration, we add node C.

And in visiting each of its neighbors,

we notice that we've now discovered a path to our destination node E.

And we have an associated distance of six.

On the final iteration, we end up adding node E to our graph and

discovering there is in fact a path from node A to node E.

Here's an outline for Dijkstra's algorithm and pseudo code.

Notice that we associate two attributes with each of the nodes in the graph,

like distance value and a parent field.

Which we end up using to discover a path from our destination back to our source.

On each iteration of the algorithm,

we choose the node in the list with the smallest associated distance values.

We update the neighbors of that node, as we described earlier.

Once the destination is removed,

we can recover a path to the start by starting at the destination node and

repeatedly moving from each node to its parent until we arrive at the start node.

The computation complexity of this algorithm is related to the number of

nodes and the number of edges in the graph.

A naive version of this algorithm can be implemented with a computational

complexity that grows quadratically with the number of nodes in the graph.

By implementing the sorted list of nodes more cleverly with a data structure known

as a priority queue, we can actually reduce the computational complexity to

a term that grows more slowly, as shown in the second equation.

So we see that the Dijkstra's procedure is a bit more expensive than grass fire but

only by a term that grows logarithmically in the number of nodes.

The basic reason that Dijkstra's algorithm works

is that we end up marking nodes based on their distance from the start node.

That is whenever we mark a node, color it red in our example,

we can be sure that there is no shorter path to that node

from the start node via any of the nodes that we haven't marked yet,

given the fact that our edge weights are in fact non-negative.

Take a minute to convince yourself that this procedure does, in fact,

find the shortest path.