%T Finding Real-Valued Single-Source Shortest Paths in o(n^3) Expected Time
%A Stavros G. Kolliopoulos
%A Clifford Stein
%R Technical Report PCS-TR95-272
%I Dartmouth College, Computer Science
%C Hanover, NH
%D October 1995
%U http://www.cs.dartmouth.edu/reports/TR95-272.pdf
%X
 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.