- [Instructor] Hi there, we're going to continue
our exploration of graphs and graph algorithms.
And today we're going to do Shortest Paths.
Now, Shortest Path is as you might expect
the shortest path between two nodes in a graph.
So if I've got node A and node B
there may be multiple paths through the graph
to get from node A to node B
and we want to find the shortest one.
And this has a lot of applications as you might expect.
Virtually any problem that we can represent with a graph,
shortest path is going to be helpful to us.
Some examples are vehicle routing,
network design, telecommunications,
and there's a substantial class of optimization problems
which we can represent as graphs
and shortest path is a part of the solution.
Now, of course, the canonical example
is maps of cities and distances between them.
So here we have a map of a portion of Southeast Nigeria
and we can identify cities in this map
that are connected by highways
and we can abstract the highways as edges
and assign weights to them
that correspond to the distances between the cities.
And so we have this abstract graph now.
And it's perfectly natural to ask questions of this graph.
For example, what's the shortest route
from Benin city to Calabar?
Or what's the shortest route from Ogoja to port Harcourt?
Is it through Ugep or Otu?
I don't know. I've never been to Nigeria.
Or is it through Owerri?
Are these are perfectly reasonable questions to ask?
And so finding the shortest path
is a natural kind of a problem.
And we can look at this two ways.
We can calculate the shortest paths
from some node call it V knot
to all other nodes in the graph
or we can have some target node that we want to reach
and we calculate the shortest path
from node V knot to this other node, call it V1.
And obviously if we've solved the first,
then we've solved the second.
So we're going to focus on the approach
where we solve the first
we find the shortest paths to all other nodes in the graph.
Now, let's take a look at this graph here.
Here we have a undirected unweighted graph
and we have node A colored here.
And in this case,
if we wanted to calculate the shortest path,
we would calculate the minimum number of steps that it takes
to get from no day to any other node in the graph.
We just count the edges that we'd have to traverse.
So we'd come up with something like this.
Yeah, there are longer paths
like I can find a path to J from A
that goes through B and H
that would have a length one, two, three
but this one's shorter just one step.
So this would be the solutions to shortest paths
in an undirected unweighted graph.
And the problem would be the same
if we had a way to graph,
if all the weights were equal to one,
we'd get exactly the same numbers.
And we could even generalize this further
to a directed graph.
Here, it's exactly the same graph
essentially as the one we saw here,
except we've represented the undirected edges
as two directed edges both at the same way,
all the way it's here one.
And so we'd come up with the same values
for the shortest path.
So the shortest path between A and B is of length one,
the shortest path between B and D is of link three,
the shortest path between A and H
is of length two and so on.
So let's look at a little simpler problem
without quite all that clutter.
So I've removed some edges here
and we still have a directed graph
and all the edge weights are the same.
And if we were to calculate again,
we'd wind up with the same distances.
But what if the edge weights were different?
If the edge weights were different
we'd have a little more complicated problem.
And here the distance of a given path
is the sum of the weights of the edges in the path.
So for example, this path
going from A to B to H has length 10,
the distance between A and H we say is 10,
because this one is seven,
this one is three, seven plus three is 10.
This path has a length of 25,
six plus one is seven, plus seven is 14 plus 11 is 25.
So this particular path from A to F
has a distance of 25.
And where we could quickly arrive at a solution
by a visual inspection of the graph
given these small problem instances
already it's not as easy to say,
what are all the shortest paths
between A and all the other nodes in this graph.
So even with a small problem instance
it starts to become pretty cumbersome.
And you can imagine the graph I showed you earlier
of the cities and highways in Nigeria,
that's even more complicated
and that too is a small problem instance.
So we need an algorithm that will work
on graphs of any size.
So allow me to introduce Edgar Dijkstra.
Back in the 1950s, Dutch computer scientist, Edgar Dijkstra
came up with an algorithm that we'll present here.
It's an example of a greedy algorithm.
We'll see what that means in a little bit.
And it solves the problem of finding the shortest path
in a graph between some node,
call it again call it V node or A
to all the other nodes in the graph.
And the story goes that Dijkstra
came up with this while he was sipping coffee
in a cafe someplace, he didn't have pencil or paper,
he just arranged things on the tabletop
and worked out a solution.
Three years later, he published it
and now it's one of the most famous algorithms
on the planet, Dijkstra's algorithm.
So that's Edgar Dijkstra.
Who's a bit of a character to, Google some of his quotes.
He's a very opinionated person.
So, how does Dijkstra algorithm work?
Well, let's say we wanted to find the shortest path
between node A and all the other nodes in this graph.
So we start by creating a set of unvisited notes
and initially that will be the same
as the node set for the entire graph.
So A, B, C, D, F, H, J, K and L that's all the notes here.
So we mark all the nodes as unvisited.
Then the next thing we do to initialize our problem
is we assign a distance of zero to our starting node
and a distance of infinity to all other nodes, okay?
And if our programming language doesn't have
infinity, then we just use an extremely large number
some number that we don't expect to encounter in our graph.
And then we start with the unvisited node.
That's the node with the smallest distance, right?
Node A has distance zero
and all the other nodes have distance infinity.
So we start with A and we calculate the distance
to all unvisited neighbors of A.
So in this case that's B and J
and we compare the calculated distance
with the current distance.
Now, the current distance are both infinity.
So when we calculate the distances,
we're going to set the distance to B, to be seven.
Seven is less than infinity.
So we're gonna update this to be seven.
And then we're gonna calculate the distance to J,
we're gonna set that equal to six.
And we're also gonna make a note of where we came from.
when we updated these distances.
We came from node A to get to B,
we came from node A to get to J,
so we update these it's gonna look like this.
The distance so far from A to B is seven.
We came from A the distance from A to J is six
we came from A, okay?
So what do we do now?
We mark A is visited.
We take it out of this set,
mark it as visited.
And now we want to find the next node
from which we're going to continue our exploration.
And we choose the next node
based on the shortest distance again.
So we've already visited A that's off the list.
So of all these remaining nodes
that are so far unvisited J has the smallest distance.
So we're gonna explore from J.
So we're gonna explore from J
we're gonna calculate the distances from J.
It turns out that we can only reach one node from J
that's H along this edge.
The edge connecting J and H has weight five,
and the distance to J we've already seen is six.
And so we're gonna calculate the distance to H as 11
but we're gonna make a note that we arrive there from J.
So there's our values for H.
The distance is 11 and we arrive there from J.
So far so good.
So let's mark J as visited
by removing it from the old visited set.
And then we're gonna find the next node to explore.
Now of all of the unvisited nodes,
the one with the smallest value is B
that's seven so we choose B.
Now from B, we can reach C and we can reach H.
Now the edge connecting B and C has weight nine,
B has a distance of seven from A
so the distance from A to C
that we're gonna calculate through this route
is going to be 16.
16 is less than infinity
and so we're gonna update the distance to C
and we're gonna note that we arrived at C from B, okay?
Now we have this edge to consider.
We can also get from B to H.
And notice that this has a weight of three
and the distance here is seven.
So we calculate the distance to H has 10.
Now 10 is less than the current distance, which is 11.
And so we found a shorter route to H.
The route through J has distance 11
but the route through B has distance 10.
So we're gonna update the values for H
to show that the distance is now 10 it's reduced by one.
And now we arrived at H from B.
We only concern ourselves with where we arrive from
for the shortest path that we've found so far.
So that finishes things for B.
We mark B as visited.
We remove it from the unvisited set
and now we hunt for the next node to work from.
And of the remaining nodes, H has the lowest value.
So we're gonna explore from H.
And from H we can only reach L by this edge of weight two.
The distance here is 10, that's going this way.
And so we're gonna calculate the distance L is 12,
12 is less than infinity.
And so we're going to set the value for L to be 12.
And we're gonna indicate that we arrived there from node H.
We're going to mark H as visited
and now we're going to find the next node to explore.
The next node is L which has the lowest value, 12.
And so we explore from L and we calculate the distances.
The only thing we can reach from, well, actually no
we have two things we can reach from L.
We can reach K and we can reach F.
So let's consider this one first.
So we have 12 here plus three equals 15,
15 is less than infinity.
So we're gonna update K to say that the distance is 15
and that we arrive there from node L.
And now let's consider this edge here that gets us to F
that's 12 plus one is 13.
13 is less than infinity.
So we're going to update that
and indicate that we arrived by the current shortest path
of 13 from node L.
We're gonna mark L as visited
and now we're gonna choose the next node
from which to explore.
The next node from which to explore is going to be F
because F has the smallest value
of the remaining vertices that are in our unvisited set.
So we start from F we calculate some distances.
The only thing we can reach is D by this edge.
So we have 13 plus seven gives us 20,
20 is less than infinity.
So we set this to be 20
and indicate that we arrived here from F.
And that's it for F so we mark F as visited
and now we just have CD and K in our unvisited set.
That's the one with the smallest value is K.
So we're gonna visit K
and we're gonna find its neighbors.
But we noticed that all of K's neighbors
have already been visited.
The only one we can reach is J
but we've already marked J as visited.
So there's nothing for us to do.
So we're just gonna mark K is visited
and remove it from set U.
So now what's next.
We have C and D left. C has a distance of 16.
So we'll explore from C.
From C we can only reach node D
but we do it along this edge, which has weight two.
So 16 plus two gives us 18.
18 is less than 20.
So we're going to update the value for D.
So the distance is 18
and indicate that we arrived at D from node C.
We're gonna mark C as visited.
Then the only thing left to pick is D.
So we're gonna explore from D and calculate the distances,
but of course all the other nodes were already visited.
So there's nothing for us to do.
We marked is visited and we're done.
The unvisited set is empty.
All the nodes have been visited
and now we know the shortest path
from A to any node in the graph.
They're are all shown here.
These are all the shortest distances.
And the distances are obvious
but how do we know the shortest paths?
Well, we kept track of the node that we arrived from
whenever we found a shortest path.
So we can use this information to recover any shortest path.
So, for example, what's the shortest path from A to L?
We know what's of length 12.
So let's start at L and work our way backward, right?
This tells us that we arrived at L from H.
So we know this edge is on the shortest path.
And now how did we get to H?
By the shortest path, we arrived from B.
So this edge is going to be along the shortest path.
And how did we get to B from A?
And so that edge is gonna be on the shortest path.
And so now we've reconstructed the shortest path from A to L
by working backwards from our partial solutions.
This is a technique that's called dynamic programming
where we save partial solutions as we go,
each of these notations of where we came from
when we arrived at the new shortest path,
those are all partial solutions.
And we use these partial solutions
to reconstruct the shortest path between A and L.
And obviously we can do that
between any node in the graph and A.
So the partial solutions
are used to reconstruct a complete solution.
This is called dynamic programming.
If you see it in other classes like CS224,
they'll make a big deal about it.
Dynamic programming sounds like a very daunting thing
but it's really very simple concept.
You save your work as you go in partial solutions
and use those partial solutions
to reconstruct a complete solution.
when you're done processing your problem.
That's all there is to it.
Again, we can do this for any pair of nodes
once we've processed the graph.
So that's Dijkstra's algorithm.
And we could pick any starting node in this graph.
We could choose B and run the whole algorithm
again or choose K or choose F, it doesn't matter.
And we'll come up with a different set of distances,
but in each case, we'll find the shortest path
that exists between some starting point in the graph
and all the other nodes in the graph.
What did you notice about how we chose the nodes to visit?
Well, we always chose the node with the smallest distance.
Now, can you think of a data structure
that's handy for always extracting the smallest value?
The answer should be, yes we've seen one already
a minimum priority queue.
And it turns out that we commonly implement
Dijkstra's algorithm using a minimum priority queue.
So let's take a look at some pseudocode.
So here's some pseudocode we've got this function,
Dijkstra it takes G and S as parameters.
G is the graph and S is the starting node.
And then for each node V in the graph,
we have this vector or a array
that stores where we arrived from.
Those are the notations of where we arrived from
to get to our partial solution.
And so we set those all to null.
If V is the starting node,
then we set the distance to V equal to zero.
Otherwise we set all the other distances to be infinite
and we add each node to the priority queue.
And the priority queue is a minimum queue.
So the minimum value is going to be at the root
once it's done all of its work
to preserve the heat border property.
And so we're ready to extract the minimum value.
Now, in the first case, it's gonna be zero
cause we've initialized the starting node to be zero
and all the others to be infinite.
So we know at the first iteration, zero is at the root.
So we have this while loop,
while the queue is not empty,
we get the minimum value from the priority queue.
We call that V.
And then for each unvisited neighbor, N of V,
we calculate that distance
which is the distance that we've already found to V
plus the distance to N along that new edge.
And if that distance is less than
what's already stored for that node,
when we start out it's going to be infinite,
but we'll update those as we go.
Then that means we've found a shorter distance
and we update it.
So how do we do the update?
We set the distance for that node to be the new distance
that we just calculated.
And we make a note of where we arrived from
which was in this case V we arrived at node N from V.
So this, my friends is a complete implementation
of Dijkstra's algorithm.
It is a very concise algorithm.
It's a very, very elegant thing.
So there's a catch.
There's always a catch, right?
What's the catch with Dijkstra's algorithm.
It only works for directed graphs
as long as all the weights are non-negative.
You can have zeros, but you can't have negative values.
And the idea is a simple one.
Dijkstra's algorithm operates on the presumption
that as we add edges to a path,
we're never going to decrease the length of a path
by adding an edge, okay?
You have a monotonically non-decreasing function
and that's a presumption of Dijkstra's algorithm.
So Dijkstra's algorithm cannot handle negative weights.
Now, of course, in the case of a map,
you're not gonna have a negative distance
from Detroit to Toledo.
They're always going to be positive values
but there are a lot of problems
for which it's reasonable to use a negative weight
along an edge.
And for those Dijkstra's algorithm doesn't work.
And what's the complexity.
Well, the worst case complexity
using a minimum priority queue,
we have to go through all the vertices.
We have to go through all the edges.
So that's the cardinality V plus the cardinality V
and we're using a priority queue.
So we have log V term here,
and this gives us the worst case complexity
for Dijkstra's algorithm using a minimum priority queue.
And as we've already noted, it's a greedy algorithm.
It always chooses the best shortest distance
that's been found so far, okay?
What really does that mean, greedy approach?
Like I said, we always choose the shortest distance
we've calculated so far,
but it's important to note that we never go back.
Once a node is marked as visited,
we never revisit it.
So we grab the best result in a greedy way.
And if we find a better one, we grab that.
We never go back to a node once it's marked as visited.
So as we go through the algorithm,
we mark these nodes as visited
and we never update them
once they've been marked as visited.
So now question, why doesn't Dijkstra's algorithm
work with negative weights?
Well, let's look at a simple example.
Here we have a directed graph,
weighted graph with a negative weight here
you see there's a negative eight here,
and let's just run Dijkstra's algorithm on it.
We're starting from node A
and what we're gonna do is we're gonna calculate
the distance to all the unvisited neighbors of A
which is B, C and D.
And we're going to get seven and we arrived from A and five.
We arrived from A and nine.
We arrived from A, okay?
Then we're going to mark A as having been visited,
and we're gonna move on to B.
Now, what happens when we look at B?
Well, we're going to see that we can reach C from B
but that's five plus five is 10 is greater than seven.
So we're not gonna update here
but we're going to mark B as visited.
So now A and B are visited.
And then we're gonna look at C
and we're gonna see that C we can get to D
but that gives us seven plus four is 11
is greater than nine and so we don't update that.
And so we mark C as visited.
And now we get to D
and we only look at the unvisited neighbors
but there are no unvisited neighbors.
And so we have nothing to do
and then we're gonna mark D is visited
but we got a problem here, all right?
And the problem is, is that we didn't discover
the real shortest paths.
We followed the algorithm to the letter,
but we didn't find the shortest paths.
Where are these shortest paths?
Well, I can go from A, to D to B
and that's nine minus eight.
So this distance should be one arriving from D
and I should be able to go from A to D to B, to C
and that'll give me a distance of six arriving from B.
So you see Dijkstra's algorithm,
when there's a negative weight
can fail to find the shortest paths.
Negatives weights do not work
with Dijkstra's greedy approach, okay?
So keep that in mind.
What else, can we do do better?
We've seen that the worst case complexity
is big O of cardinality V
plus the cardinality V times the log of the cardinality V.
Can we do better than that?
Well, in special cases, we can.
So here in the graph above it has the same node set
as the graph that we saw earlier
but I've rearranged the edges so as to remove cycles.
So the graph that we worked our example on had cycles in it,
this one is a cyclic
and you'll recall that for every directed acyclic graph,
there's at least one top illogical sort.
And so here we have a directed acyclic graph
and below is just rearranging the vertices
to show a topological sort for this graph.
So we have A, B, C, D H L K J and F in that order.
And so that provides us with a convenient linear order
to our vertices.
And we can proceed through these nodes in a linear fashion
and we don't need to maintain them in a priority queue.
So the overhead of working with priority queue is gone.
And so this makes this a little faster.
So in the case of a directed a cyclic graph,
we can perform a little better.
Now, why does this work?
Well, because nothing ever goes backward, right?
In the directed acyclic graph,
once we produce a topological sort,
everything if we're starting at A,
everything to the right of A,
we're always moving in the same direction,
we never go backward.
And because we never go backward,
we never have to worry about updating distance
to a node that we've already visited.
So this gives us the order
in which we're gonna visit our nodes
and we don't have to worry about priority queue.
So in that case, the worst case complexity
in a directed acyclic graph using topological sort
is the same as the complexity for topological sort.
It's big O of the cardinality V
plus the cardinality V.
So that's kinda cool.
So in summary, Dijkstra's algorithm is a greedy approach.
We grab the best answers so far, and we never backtrack.
It's a dynamic programming approach.
We save partial solutions along the way
and reconstruct complete solutions
from the partial solutions.
That's how we were able to say
what the shortest path was between A and L
in the example that we worked out
we went to L and we worked backward
through all those pointers until we got back to A
reconstructing the complete solution.
Now, what about negative weights?
Well, negative weights are for another day.
There's an algorithm called the Bellman-Ford algorithm.
It runs in, I believe it's a big O
of the cardinality V times the cardinality of E.
And so it's slower than Dijkstra's algorithm
but it can handle negative weights.
And I'll either do a separate lecture
on that, a supplemental lecture, or you'll see it in 224.
So that's all for now, thanks.