Good morning or good afternoon.
I am Esteve Codina and I am going to present this video,
shortest path problems, within the block number six
algorithm & graphs, some elementary concepts.
The contents of this video
will go as follows: we have an introduction.
We will see the formulation of the shortest path problem.
We will see the Dijkstra's algorithm from solving shortest
path problems, and we finally see
key learning concepts, give some references and block extensions
and also proposals for solving further problems,
and other examples.
Okay, the learning objectives is to have an example
of a real algorithm working on a graph described with a pseudocode.
We saw what
a pseudocode code is in the previous video.
We next will go in the calculation of shortest paths
on directed graphs,
using Dijkstra's algorithm, we will describe this algorithm
and then trace the paths
so calculated using data structures required by the algorithm.
Well, this problem is
a central problem used widely in modeling urban networks using graphs,
and they are useful also for more complex problems, like, for instance,
the traffic assignment problem.
As we saw in the previous video,
that graphs are a powerful tool for expressing
characteristics and topology of urban networks.
Usually in this graphs
ee have associated costs on the links of the graph, either
travel times, economical costs
or abstract generalized costs.
Okay, so let's see the the formulation of the shortest path problem.
Let's consider a directed, connected graph made up by a set of nodes with directional
links with non-negative are costs which will be expressed by 'cij'
where (i,j) is a link in the set of links.
So the shortest path problem can be stated as if we have two nodes, one the origin
and the other, the destination, inside of the set of nodes
we have to find the sequence of links forming, forming a path,
and the sequence of links will be expressed as a sequence of 'a1',
'a2', 'a3' ... 'an', which will start at 'o' and will end at 'd'.
So the sum of costs of the links making up the path has the minimum possible value.
Okay, so
let's see that the
data structures we need for for the shortest path algorithm
that we will describe.
It will be assumed that the graph is stored in data structures that the given a node 'i'
allows easily to access to the neighbors nodes
of that node forming the forward star.
We saw that what the forward star is in
a previous video. For instance, the forward start of node
i=6 will be nodes 7 and 8, which are the head
nodes of the arrows, or of the links emanating from node number 6.
We will designate the forward star by 'E[i]'
right?, enclosing 'i' in brackets.
Okay.
So Dijkstra's algorithm actually solves the following problem.
If we can see the connected, directed graph with non-negative arc costs
and we have a source or node 's',
this algorithm
finds one shortest path from 's' to any other node in the graph.
So if there are n nodes , the Dijkstra's algorithm,
will find n-1 shortest paths.
This algorithm provides this n-1
shortest paths in the form of a spanning directed, out-tree,
with root at node 's', that visits any other node in the network.
Remember that a directed out-tree
can be stored using a predecessors vector,
as we saw in the previous video,
and in the slide
we see for instance, a directed out-tree tree with root at node number 1
in the predecesors vector for
indicating which is the set of paths containing the directed out-tree.
So, what do
we need initially? we need the label of the origin node
the algorithm we'll use set 'S'
of candidate nodes to be examined at each step.
We will set initially, this 'S' equal
to the set of nodes in the network.
Next we will have to
make use of an array 'd' of as many positions
as nodes we have in the network, and this array will contain
the current distances of the nodes to the source node 's'.
We refer to that it as the distance label
array.
Also, we will need an array for the predecessors
that will be updated throughout the course of the algorithm.
And we
have here an outline of how this algorithm works.
Basically, the algorithm selects a given node
in the set of candidate notes, 'S',
but not an arbitrary node within 'S', but that with the shortest distance
'd(i)' and then it scans the forward star of that node 'i', and checks
whether it's for each element in the forward star
if it's worth to updating its distance label or not.
Yeah.
So it compares the distance label
'd(j)' that currently has with distance label that would result if 'i' was
the predecessor of the node 'j', which would then
be d(i) + cij.
Well, so then if this happens the processor of node 'j'
is temporarily the node 'i' and it's known
that if this procedure it is followed using always
the shortest distance labeled node 'i' in the set 'S', the note 'i'
will never be examined again and it can be taken out from
the set capital 'S'.
As output,
the algorithm will provide distances 'd'
to the source node and the directed spanning out-tree
stored in the vector of processors.
Okay.
We see here the shortest path algorithm formalized as a 'pidgin' code.
We have its initialization step, in which we said that we set all the distance labels
to infinity for any arbitrary node in the network, excluding the source,
which has naturally a zero distance label.
We also put some mark into the position
of the source node in the predecessors vector, such as 0 or NULL.
And we initially set that the set of candidate nodes
is the entire set of nodes 'N'.
So the iterative step would
be as follows. While we have
that the candidate of nodes is not empty, i.e. there are some nodes in there,
We select a given node in the candidates it of nodes,
but not any arbitrary node,
but the one with the smallest distance label to the to the origin 's'.
Yeah.
Then because we know that the node I will never be visited again,
then we can take it out from the
set 'S' and for that node 'i'
we examine the elements of the nodes in the forward star,
and make the comparison between in this 'if' statement,
the comparison between the current distance label 'd(j)'
it has, with the label that it would result from updating
the predecessor of the node 'j' being node 'i'.
So if actually 'd(i)' plus the cost
from directly going from 'i' to 'j', is smaller than the distance label
'd(j)', what we do is we update the predecessors vector and we change the label
of the element 'j' in the forward star of of 'i', and this we do for
any element in the forward of 'i'. This would be the general iterative step.
Okay, so let's see how this works using an example.
Imagine that we have as an root node 's', node number one,
and here we see the costs on the graph.
Okay.
So each of these slides that we would present
is the end of the while
iterative statement
of this algorithm.
So initially it's extracted the node number one, the root
node, and its forward star is examined.
Notice that after the first iteration
the labels of node number 2, node number 5 and number 3
have become finite, right?, and equal to the costs
of reaching node 2 directly from node 1 of reaching 5
directly from node 1 and 3 directly from node 1. Yes?.
So the the distance label of node number 2 is now 28.
Node number 5 is 1, and node number 3 is 2.
All other nodes in the graph
have infinite label
because they have not yet been examined.
Okay, so now we will have to focus on
which is of these three nodes has the smallest possible label.
Also, notice that by now
the predecessors of node 2, 5 and 3 are node number one.
Yeah?.
So from the labels of node number 2, 5 and 3, we see that
the smallest label is that corresponding to node number 5.
So node number 5
will be the one selected for examining its forward star.
So we then go and examine the forward star
of node number 5, which are nodes number 2 and number 6.
And we see that for node number 2, it was removed its distance label
because now by making that 5 is the predecessor of node number 2,
it has a smaller label. Yeah.
So that way the the link from 1 to 2 is in dashed line.
Yeah.
So after the end of
of the second pass we see that the labels of the nodes
are marked as appears in the slide.
Yeah?.
So only finite labels are at node number 2
node number 6 a node number 2, number 3, sorry
And these are 9, 27 and 2.
The smallest label
is that corresponding to node number 3.
So node number 3 will be the one selected to be examined
for it's forward star.
Okay. So, from node number 3, it's
forward star are nodes number 6 and node number 8,
it can be seen that node number 6 achieves
the smallest label if predecessor of node number 6 is node number 3
and then node number 8, has a finite label, right?
Okay. So, now we have that,
finite labels appear at node number 2, Node number 6 and node number 8
Yes.
So the smallest of them ... corresponds to node number 2.
So node number 2 will be
the one that will be examined to to scan its forward label.
Also, notice that the
predecessor of node number 6 now is node number 3 and previously was node
number 5, and this needs to be updated in the predecessors vector.
So, let's go for node number 2. Node number 2 has
these two elements in the forward star:
node number 4 node number 6, which have now these
smaller labels, 18 and 19.
Node number 6, which had previously as predecessor node number 3 has now
predecessor node number 2.
Okay, so now we have that nodes
with finite label we have node number 4,
node number 6, node number 8 with 18, 19, 29, respectively.
The smaller of them is for node number four.
with label 18.
So, now node number 4 will be the one examined for its forward star.
We see at node number 4 and then, well,
node number 4 has as forward star node number 5, 7, and 8.
Node number 5 is examined, but it's not worth to lower
its label, being 4 its predecessor
because it's already one, you know, that has been examined.
So, it's impossible that it could happen like that.
Instead, node number 7 and node number 8 have its
label lowered and result in a smaller label.
So, now predecessor
of node number 7 and node number 8 is the node number 4.
Okay.
From them all, we see that the smallest of them is at node number 6.
So node number 6,
will be chosen now
to examine it's forward star.
Number six and...
its forward star is made up by node number 7 and number 8.
Node number 7 had already a smaller label that
it would be obtained
by putting node number 6 its predecessor,
node number 8 now results in a smaller label.
Right.
Okay.
So from all nodes with a finite label, we have
node number 7, and node number 8, being
the smallest of them
that corresponding to node number eight with label 20, right?
So we examined node number 8.
It has no forward star: nothing to examine.
So, the only one remaining in the set 'S'
is node number 7.
node nmber 7 has to be examined now and then,
with the only element of forward star of node number 7 is node number 8
But actually its label, it's already the smallest possible.
So we have finally examined all the nodes in the in the in the graph.
So at the end of the algorithm and yeah, and this is the solution, right?
So we see marked in
bold, links and bold arrows, the links of the
directed out-tree and you can check that the cost of this spanning directed out-tree
is 39. you'll probably not be able to find the smaller spanning tree with
shorter cost
and well we can see here in this slide
the summary of the operations that we have been describing,
as a tracing of the algorithm, check that they are correct.
So finally we got into this
reference Ahuja, Magnanti and Orlin, network flows,
which is a classical for mathematical programing on network flows.
See chapter number 4 in which we see the descriptions
we have made in this video, and chapter 13 for an application of them.
Also as an extension, you will find the same book
Chapter number 5, in which you will see algorithms which are similar
to Dijkstra's algorithm, but just similar because they have
other features.
Okay.
So in the material, you will see examples solved
for instance, as this one.
Yeah, try to solve it and you will find the solution
in the reference material and in these slides.
So that's all, thank you very much for your attention.