@TechReport{Dartmouth:TR95-272,
  author = {Stavros G. Kolliopoulos and Clifford Stein},
  title = {{Finding Real-Valued Single-Source Shortest Paths in o(n^3) Expected Time}},
  institution = {Dartmouth College, Computer Science},
  address = {Hanover, NH},
  number = {PCS-TR95-272},
  year = {1995},
  month = {October},
  URL = {http://www.cs.dartmouth.edu/reports/TR95-272.pdf},
  abstract = {
    Given an $n$-vertex directed network $G$ with real costs on the edges
    and a designated source vertex $s$, we give a new algorithm to compute
    shortest paths from $s$.  Our algorithm is a simple deterministic one
    with $O(n^2 \log n)$ expected running time over a large class of input
    distributions.
      The shortest path problem is an old and fundamental problem with a
    host of applications.  Our algorithm is the first strongly-polynomial
    algorithm in over 35 years to improve upon some aspect of the running
    time of the celebrated Bellman-Ford algorithm for arbitrary networks, 
    with any type of cost assignments.
  }
}