[Subject home], [FAQ], [progress],   Bib', Alg's,  C , Java - L.A., Friday, 29-Mar-2024 13:06:26 AEDT
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

Single-source shortest path(s) problem

NB. Only works for non-negative edge weights.

Dijkstra's single source shortest paths algorithm

Shortest Paths

Imagine the algorithm part-way through solution.  Invariant (Inv):


Can guarantee Invariant is true initially:

shortest paths

How to make the set, done, bigger?

Paths

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.


©
L
.
A
l
l
i
s
o
n
[run demo'; class: take notes!]   Dijkstra's single source shortest paths algorithm:
-- Graph G = <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.

Warshall's Transitive Closure Algorithm

Note

One solution would be to form   A or A2 or ... 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.

Floyd's all-pairs shortest paths algorithm

[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.

Graphs:   Paths:   Summary

-- for a graph represented by an adjacency matrix.


Prepare:

© L.Allison, Friday, 29-Mar-2024 13:06:26 AEDT users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/15paths.shtml
Computer Science, Software Engineering, Science (Computer Science).