Graphs:   Paths:   Introduction

• Saw the different types of (un)directed, (un)weighted Graph & examples.   Now . . .
  
  
• Path algorithms for directed graphs:
  
  
• A path is {v₁, v₂, . . ., 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 / connectedness: can I get from v_i to v_j? (Warshall)
  
  
• Problem:   What is the shortest path from v_i to v_j? (Dijkstra, Floyd)
  
  

Single-source shortest path(s) problem

• 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

NB. Only works for non-negative edge weights.

Dijkstra's single source shortest paths algorithm

• 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____________________________________?]
    
    
• Once we find a genuine shortest path from v_i to v_k, we never need to revise our opinion of it.

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

• 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} where v_i, ..., v_k are in done and 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".
  
  

How to make the set, done, bigger?

• 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 problem because . . .
    
    
• 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 . . .

• . . . either
  
  
  • v_i, v_p, . . . , v_r, v_c where v_p . . . v_r are in done is a shorter path
    
    
  • but that is impossible because [_____________________]
    
    
• or
  • v_i, v_p, . . . , v_r, v_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 {v_i, ..., v_k, v_u} where v_i, ..., v_k are in done and v_u is in V-done";  see 'update ...' below.

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'

Warshall's Transitive Closure Algorithm

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

Note

• Adjacency matrix A_i,j represents every path consisting of one edge
• Matrix A² represents every path consisting of two edges . . .
• Matrix A^m represents every path consisting of m edges

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'

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

Graphs:   Paths:   Summary

• Single source shortest paths, Dijkstra, O(|V|²)-time
  
  
• All-pairs shortest paths, Floyd, O(|V|³)-time
  
  
• Transitive closure (connectedness), Warshall, O(|V|³)-time
  
  

-- for a graph represented by an adjacency matrix.

Prepare:

• Minimum spanning trees of undirected graphs.