Tuesday, August 16, 2005

All pair shortest paths on directed graphs

The textbook algorithms for APSP assume a weighed directed graph. The algorithms are the following:

  • Dijkstra: basically a SSSP for each vertex: assumes no negative weight edges. running time O(V^3).
  • Dijkstra: better data structures: using binary min-heap: O(VE* lg V).
  • Dijkstra: better data structure: using Tarjan's Fibonacci heap: O(V^2*lg V + V*E).
  • Bellman-Ford: Also a SSSP from eaqch vertex, however, allows negative weight edges. running time: O(V^2*E) (this could be O(V^4) on dense graphs).
  • Bellman-Ford: improved running time
  • Floyd-Warshall: uses the repeated squaring algorithm Very similar to transitive closure running time: O(V^3).
  • Johnson: An improvement for sparse graphs. uses both Dijkstra's algorithm and Bellman-Ford algorithm as subroutines. Uses a reweighing technique. O(V^2* lg V + VE)

    Convergence of a PDE??
    equivalence of two SUREs
    Predicting the final values without computation???
  • No comments: