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

- Path
algorithms for directed graphs:

- A path is
{v
_{1}, v_{2},. . ., v_{i}, v_{i+1},. . ., v_{n}} such that each <v_{i}, v_{i+1}> is in E, i.e. is an edge.Length / weight of a path is summed over its edges.

**Problem:**Closure /**connected**ness: can I get from v_{i}to v_{j}? (Warshall)

**Problem:**What is the shortest**path**from v_{i}to v_{j}? (Dijkstra, Floyd)

- What is the shortest path from a given
v
_{i}to a given v_{j}?

- Turns out shortest paths from v
_{i}to*all other vertices*is as easy.

- Hence single source (& all destinations).

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

- dynamic programming

- greedy

- dynamic programming

**NB.** Only works for non-negative edge weights.

- Key (dynamic programming) observation:

- if P =
{v
_{i}, v_{j}, . . . , v_{k}, . . . , v_{m}} is a shortest path from v_{i}to v_{m}

- then Q =
{v
_{i}, v_{j}, . . . , v_{k}} is a shortest path from v_{i}to v_{k}

- [why____________________________________?]

- if P =
{v
- Once we find a genuine shortest path from
v
_{i}to v_{k}, we never need to revise our opinion of it.

- Knows shortest paths from source v
_{i}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*{v_{i}, ..., v_{k}, v_{u}} wherev are in done and_{i}, ..., v_{k}v _{u}is in V-done.

Can guarantee Invariant is true initially:

- done = { v
_{i}} -- the source

- The first shortest path from v
_{i}to "somewhere else"

must consist of the shortest edge from v_{i}to "somewhere else".

- choose vertex in V - done
that is closest to the source, v
_{i}.

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

*Happens*to give an optimal solution in this problembecause . . .

- It is a "local" or "immediate" choice,
hence "greedy".
- Suppose this step chooses v
_{c}- i.e. short path
v _{i}, v_{j}, . . . , v_{k}, v_{c}*where*v _{i}, v_{j}, . . . , v_{k}*are in done.*

- This
*must*be the shortest path from v_{i}to v_{c},otherwise . . .

- i.e. short path

- . . . either

v v_{i}, v_{p}, . . . , v_{r},_{c}where v_{p}. . . v_{r}are in done is a shorter path

- but that is impossible because
[_____________________]

- or
v v_{i}, v_{p}, . . . , v_{r},_{c}is a shorter path where one of v_{p}. . . v_{r}, say v_{q}, 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
_{i}, ..., v_{k}, v_{u}}_{i}, ..., v_{k}_{u} is in V-done"

© L . A l l i s o n |

-- Graph

-- P[i] is the best (known) path length from source to vertex i

done := {v[*] Need to store more information to recover edges in paths as well as costs._{1}} -- source is v_{1}, 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 v_{1}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'

**Problem**: Is there a path from v_{i}to v_{j}?- i.e. Are v
_{i}and v_{j}*connected*?

- Adjacency matrix A
_{i,j}represents every path consisting of*one*edge - Matrix A
^{2}represents every path consisting of*two edges*. . . - Matrix A
^{m}represents every path consisting of*m edges*

[run demo'; class: take notes!]

`--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][*] Need to store more information to recover edges in paths.orC[i,k]andC[k,j] -- [*] end for end for end for --NB.run demo'; make notes

- very, very similar to Warshall's algorithm!

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

- `and' ---> `+'

- `or' ---> `min'

-- 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] :=[*] Need to store more information to recover edges in paths as well as costs.min(F[i,j], F[i,k]+F[k,j]) --?does k help? [*] end for end for end for --NB.run [demo']; make notes

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

- Minimum spanning trees of undirected graphs.