All language subtitles for 02_1-3-dijkstras-algorithm.en

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.