[Subject home], [FAQ], [progress],   Bib', Alg's,  C , Java - L.A., Sunday, 28-Nov-2021 04:40:52 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

• Saw the different types of (un)directed, (un)weighted Graph & examples.   Now . . .

• Path algorithms for directed graphs:

• A path is {v1, v2, . . ., vi, vi+1, . . ., vn} such that each <vi, vi+1> is in E, i.e. is an edge. Length / weight of a path is summed over its edges.

• Problem:   Closure / connectedness: can I get from vi to vj? (Warshall)

• Problem:   What is the shortest path from vi to vj? (Dijkstra, Floyd)

### Single-source shortest path(s) problem

• What is the shortest path from a given vi to a given vj?

• Turns out shortest paths from vi to all other vertices is as easy.

• Hence single source (& all destinations).

• Dijkstra (1959) gave an algorithm which can be classed as

NB. Only works for non-negative edge weights.

### Dijkstra's single source shortest paths algorithm

• Key (dynamic programming) observation:

• if P = {vi, vj, . . . , vk, . . . , vm} is a shortest path from vi to vm

• then Q = {vi, vj, . . . , vk} is a shortest path from vi to vk

• [why____________________________________?]

• Once we find a genuine shortest path from vi to vk, we never need to revise our opinion of it.
Shortest Paths

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

• Knows shortest paths from source vi to other vertices in a set, 'done'.

In fact has a tree of shortest paths from the source to other vertices in done.

• And knows all shortest paths of the form {vi, ..., vk, vu} where vi, ..., vk are in done and vu is in V-done.

Can guarantee Invariant is true initially:

• done = { vi }     -- the source

• The first shortest path from vi to "somewhere else"

must consist of the shortest edge from vi to "somewhere else".

shortest paths

### How to make the set, done, bigger?

• choose vertex in   V - done   that is closest to the source, vi.

• Greedy:
• It is a "local" or "immediate" choice, hence "greedy".

• Happens to give an optimal solution in this problem because . . .

• Suppose this step chooses vc
• i.e. short path vi, vj, . . . , vk, vc where vi, vj, . . . , vk are in done.

• This must be the shortest path from vi to vc, otherwise . . .
Paths
• . . . either

• 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:
-- 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

• Problem: Is there a path from vi to vj?
• i.e. Are vi and vj connected?

### Note

• 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 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
```

### Floyd's all-pairs shortest paths algorithm

• very, very similar to Warshall's algorithm!

• Replace "adjacent to" with "how far to".

• `and'   --->   `+'

• `or'     --->   `min'
[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

• Single source shortest paths, Dijkstra, O(|V|2)-time

• All-pairs shortest paths, Floyd, O(|V|3)-time

• Transitive closure (connectedness), Warshall, O(|V|3)-time

-- for a graph represented by an adjacency matrix.

### Prepare:

© L.Allison, Sunday, 28-Nov-2021 04:40:52 AEDT users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/15paths.shtml
Computer Science, Software Engineering, Science (Computer Science).