[Subject home],
[FAQ],
[progress],
Bib',
Alg's,
C ,
Java- L.A.,
Friday, 03-May-2024 08:39:48 AEST Instructions:
Topics discussed in these lecture notes are examinable
unless otherwise indicated.
You need to follow instructions,
take more notes &
draw diagrams especially as [indicated] or
as done in lectures,
work through examples, and
do extra reading.
Hyper-links not in [square brackets] are mainly for revision,
for further reading, and for lecturers of the subject.
Graphs: Paths: Introduction
Saw the different types of (un)directed, (un)weighted
Graph
& examples.
Now . . .
vi, vp, . . . , vr,
vc
where vp . . . vr are in done
is a shorter path
but that is impossible because
[_____________________]
or
vi, vp, . . . , vr,
vc
is a shorter path where one of vp . . . vr,
say vq,
is not in done
but that is impossible because
[_____________________]
So we are OK -- provided we can restore
"And knows all shortest paths of the form
{vi, ..., vk, vu}
where vi, ..., vk
are in done and vu is in V-done";
see 'update ...' below.
[run demo'; class: take notes!]
Dijkstra's single source shortest
paths
algorithm:
-- GraphG = <V, E>
-- P[i] is the best (known) path length from source to vertex i
done := {v1} -- source is v1, here
for vertex i in V-{1}
P[i] := E[1,i] --i.e. direct edges else "infinity". [*]
end for
loop |V|-1 times
find closest vertex to v1 in V - done
done +:= {closest}
for vertex j in V - done
P[j] := min(P[j], --update knowledge on shortest paths,
P[closest]+E[closest,j]) --perhaps better?[*]
end for
end loop --NB. run demo'
[*] Need to store more information to recover
edges in paths as well as costs.
Adjacency matrix Ai,j represents every path
consisting of one edge
Matrix A2 represents
every path consisting of two edges . . .
Matrix Am represents
every path consisting of m edges
One solution would be to form
A or A2or ... or A|V|
in O(|V|4)-time.
But we can do better . . .
[run demo'; class: take notes!] Warshall's
closure
alg'--Graph G = <V, E>
C := E;
-- C[i,j] := {<i,j> in E} where i&j in {1..|V|} -- [*]
-- i.e. direct edges only
for vertex k in 1..|V| do
--Invariant: C[i,j] iff there is a path i--->j direct or
-- via vertices in {1..k-1} only
for vertex i in 1..|V| do
for vertex j in 1..|V| do
C[i,j] := C[i,j] or C[i,k] and C[k,j] -- [*]
end for
end for
end for --NB. run demo'; make notes
[*] Need to store more information to recover
edges in paths.
[run demo'; class: take notes!] Floyd's all-pairs shortest
paths
-- G = <V, E>
F := E; --initialise the result Graph edges F [*]
for vertex k in 1..|V| do
--Invariant: F[v1,v2] is shortest distance from
-- v1 to v2 possibly via vertices in {1..k-1}.
for vertex i in 1..|V| do
for vertex j in 1..|V| do
F[i,j] := min(F[i,j],
F[i,k] + F[k,j]) --?does k help? [*]
end for
end for
end for --NB. run [demo']; make notes
[*] Need to store more information to recover
edges in paths as well as costs.