Today we continue Section 4.4, on three single-source SP algorithms.

    Dijkstra: no neg edges, IndexMinHeap, near linear time
    Acyclic:  neg edges OK, topological sort, linear time
    Bellman Ford: neg OK, multiple passes, O(VE) versus O(V+E)

Resuming slides:
 p 32, Dijkstra code, needs IndexMinPQ (just like non-lazy Prim)
 p 35, four traversal algorithms as instances of "priority first search"
 p 40, DAG SP code, relax edges out of each vertex, in topological order
       allows negatives, so we can also compute "longest paths" in DAG,
 p 43, application: "critical path method" for job scheduling
 p 48, negative cycles cause trouble
 p 49, the simplest algorithm! repeat V times: relax every edges
 p 51, same worst case, but butter: Bellman-Ford, vertex FIFO (like BFS)
 p 54, summary
 p 55, negative cycle detection (find by traceback in Bellman-Ford)

Some running code examples:
    cd ../book
    run DijkstraSP tinyEWD.txt 0        # can vary start vertex s=0
    run AcyclicSP tinyEWDAG.txt 5       # DAG, all reachable from s=5
    run AcyclicLP tinyEWDAG.txt 5       # same DAG, longest paths instead
    run BellmanFordSP tinyEWDn.txt 0    # works with negative edges
    run BellmanFordSP tinyEWDnc.txt 0   # detect a negative cycle

The book does not say much about "all-pairs" SP algorithms, so that
could be something we consider in homework.  There may not be time
today, but I'd like to say a few words about SP algorithms beyond
the textbook:

  "A* search": find a path from s to t, taking advantage of a function
     h(x), which estimates the distance from x to the destination t.
     This can avoid searching a huge graph (For example, given a huge
     road map of the USA, how quickly find a shortest path from
     Atlanta to Boston?)

  "Johnson's Algorithm": find all-pairs shortest paths, in a graph
     with negative edges but no negative cycle.  Works by one
     application of BF, and then V applications of Dijkstra.  So
     roughly O(V E log V) total time.

  "Floyd-Warshall": find all-pairs shortest path information,
     for dense graphs (using matrices), neg edges, in O(V^3) time.
     This does *not* relax edges (it combines paths instead).
     Not in textbook, but their website does provide source, see
     ../book/FloydWarshall.java

Both A* and Johnson use the following trick: assign a "height" h(x)
to each vertex, and for each edge (x,y), redefine its weight to be
    w'(x,y) = w(x,y) + h(y) - h(x)
This does not change the sequence of edges in any shortest path!  They
do this either to eliminate negative edges (Johnson) or to prefer
edges leading towards the target t (A*).