Hello everyone. In the lecture of Data Structure and Algorithm, we’re going to learn
Chapter 7 Graph. Today we’ll learn a very important kind of
graph algorithms to solve shortest path problem. We’ll introduce 2 methods. Let’s first see
the problem of single-source shortest path. The single-source shortest path problem is
given a source node in a weighted graph without negative weights,
how to figure out the shortest distance from it to all the other nodes.
One of the shortest path algorithm is
Dijkstra, it’s a greedy algorithm.
We divide all the elements into 2 groups,
the first group is nodes we know the shortest path to, named visited group, and the second group is which not, named unvisited group.
And each time, for adding more nodes
to the visited group, we check all the nodes
in the unvisited group and choose
the node with the smallest shortest path from the source node.
And we’ll add this node to the visited group.
We’ll greedily repeat this process, until
all the nodes are in the first group or there are only nodes not reachable from the source node remained. Let’s see this example.
First we’re going to see V0,
it’s reachable from itself, so the shortest path to it is 0, and those to all the other nodes are infinity.
When we add V0 to the visited group, and
all the nodes adjacent to it will
have a current shortest path distance, but not the final one. We record them,
and we choose the node with minimal Dist value
from the nodes not in the visited group,
and add it into it. And in our example, we add
V2. After adding V2, we’re going to modify
the Dist values of nodes adjacent to it. Of course,
sometimes we may not need to modify it, but sometimes we need. For example,
the Dist value of V3 was infinity, but after adding V2,
the Dist value becomes 25.
Then we’ll find another node
with minimal Dist value not in the visited group.
And this time, we’ll add V1 to it.
After adding it, we should check whether there are some Dist values should be modified.
We’ll add node with minimal Dist value to the visited group repeatedly,
until all the nodes reachable from the source node are processed.
The nodes which are not reachable keep
Dist values of infinity.
That’s the iteration step of this algorithm.
Let’s see the entire algorithm.
First, we’ll introduce the Dist class. The class stores the
length of the current shortest path and the previous node of the current node.
At the beginning, we’ll do some initialization work, marking all the nodes as unvisited.
And also, we set all the Dist values to infinity,
and set the previous node of every node to
source node. And we set the Dist value of the source node
to 0, and insert it
to an empty heap, that is the only element in the heap now is the source node.
We’ll repeat the loop process n times,
each time we want to get an element in unvisited group,
and its Dist value is minimal, I repeatedly add
node to the visited group. If the all the nodes besides the source node are reachable from it, the loop process should be repeated exactly n times.
If there are nodes unreachable, the algorithm will exit halfway and keep the Dist values
of unreachable nodes infinity. Let’s see the heap.
If the heap is not empty,
then we take the minimal element from the top of the heap,
and we’ll check whether this node
is visited. If not,
we have found the node we need.
Otherwise, we’ll take a new element from the top again.
We’ll explain the detail later.
If we can’t find a
node with minimal Dist value,
that is we can’t find an unvisited node until the heap is empty.
That means there are some nodes unreachable. We haven’t repeated the process n times, and that means not every node
have been a candidate for the node with minimal Dist value.
At this time, if there are unreachable nodes, we’ll keep the
the value of unreachable and stop. If we find one,
we’ll name it v and mark it as visited.
Then we’ll add it to visited group, and
see the nodes adjacent to v.
If the old Dist value of this node
is greater than Dist value of v plus
the length of the edge from v to it, that is the
total length of these two edges is smaller than the third edge, which is the length of the old shortest path.
We’ll use the shortest path via v
to replace the old shortest path.
Meanwhile, we’ll change the previous node to v. At this time,
we’ll insert the smaller length of shortest path
to the heap. We should mention that
we will not delete the value corresponding to
the old value, but directly insert a smaller value to it.
This is a correct, since if this node
have minimal Dist value, the
new value is smaller than the old value,
so it’ll be taken earlier than
the old value. And when the old value is taken,
we’ll check here that whether
the node with the old value
is visited. Since the smaller value has
been taken and the node was visited, the old value will be directly discarded.
This can make us
not always need to remove the old value and insert the new value.
Let’s see the time complexity of Dijkstra. Every time,
we mainly change the Dist value of one node. We don’t remove old value but insert new value.
In the worst case, the number of elements in the heap
may be equal to the number of edges, so the time complexity of every operation is log(|E|).
Since we need to maintain the property of heap, the time complexity of the entire algorithm is
Θ((|V|+|E|)log(|E|)).
For the graph algorithm, we should answer following questions.
The Dijkstra is designed to deal with undirected graphs, but it can also handle undirected graphs.
And it can also handle unconnected graphs and cyclic graphs.
But the graph with negative weights cannot be supported.
Let’s see the example with cycle of negative weight, that will make
the length of the shortest path to be negative infinity.
If there is not cycles with negative weight but edges,
it will also produce wrong answer due to the aftereffect. For example,
if the weight from A to C is 6,
it’s smaller than that of A to B, so according to the previous algorithm,
we’ll know the length of the shortest path to C is 6, it is no need to recalculate it.
But if there is negative weights in the graph, the length of path through AB and
BC is 2. That is smaller
than the length of AC. This is an example of aftereffect. We know that
dynamic programming is only applicable to problems with
overlapping subproblems and no aftereffects.
And greedy algorithm is a special case of dynamic programming,
so the problem should also be with no aftereffects. Thus
the Dijkstra algorithm cannot handle graph with negative weights.
There is some ways to handle this situation,
you can find them yourself. Let’s see the problem of all-pairs shortest paths.
Can we use the algorithm introduced before to solve it?
Of course. We can make every node the source node,
and run the single-source algorithm n times. Here, we’re going to introduce Floyd algorithm.
It’s a typical example of dynamic programming.
The idea of the algorithm is, first
we initialize a adjacent matrix. In the matrix,
we save the weights of edges
in it. And we iterate n times.
Each time we’ll choose a node for transfer,
and check whether we can modify the shortest path from i to j from the previous round.
And after iterating n times, every node has been considered as
transfer node, so the algorithm calculate shortest path between all pairs.
Let’s see the possible cases of shortest paths.
One possible case is that
in the kth iteration, we’ll get such a matrix.
The matrix of kth iteration is based on
the matrix of (k-1)th.
The new shortest path may be a path
using Vk for transfer. But
sometimes, we don’t need a transfer Vk,
so we still keep the value of the last iteration.
And sometimes, Vk is used as a transfer node.
In this case, we connect
the shortest path from i to k and the shortest path from k to j,
and the length of new path is smaller than the old path, so we replace the old one by it.
That is the whole process. Let’s see
the example. The initial matrix is like this.
Row 0, column 0 and the diagonal is not needed to be modified.
Let’s see the shortest path
from V2 to V1. After introducing V0,
we can shorten the length of path from V2 to V1. The original
value is negative infinity, that means unreachable. And now it changes to a shortest path with length 7.
When introducing V1, there is a similar case.
We can modify the shortest path
from V0 to V2.
And we’re going to introduce V2, and after
that, we can see we’ll
shorten the length of the shortest path from V1 to V0
from 6 to 5. And after introducing all the nodes,
the shortest paths between all paris are calculated. And
the algorithm keeps the route of every path.
Let’s see the algorithm itself. First we should do some initialization work.
We set all the lengths of shortest paths from i to i
to 0. And set the pre value to itself.
Then, for every pair with
different starting node and terminal node,
that is for every pair of different i and j, we set the
shortest paths to infinity, And set the pre values to -1.
Then we consider all the edges.
We set the values of all the node pairs with direct edges to the length of edges.
And once we introduce new node, we can update the length of the shortest paths.
For the new nodes, we’ll introduce
all the nodes in the graph one by one as new node.
And when introducing, we check all the i,j pairs,
that is we check the whole adjacent matrix,
and see whether the total length of 2 parts
of shortest paths is smaller than
the length of original path
between i and j. If true, that is
the total length of two edges is smaller then the length of third edge, we’ll modify
the old one to the new one. The edge we used here is actually a path. And then we set
the pre value to the value Vj keeps.
The time complexity of Floyd algorithm
is obvious. For we use triple loops, so the complexity is Θ(n^3).
Here are some questions. The first one is we use min heap to find the minimal Dist value.
If we don’t use min heap, but use loop to find
the minimal value, what is the complexity?
We should discuss this question in both sparse graph and density graph.
And in Floyd algorithm, it keeps
the pre value and use the first
form. If we change it to
save the node
with minimal number v.
So how is it? Is that
possible? Of course. It will not affect the calculation of length.
And also, we can restore the route.
But the complexity of restore is
different. Let’s think about which one is better.
Thank you all.