BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR95-272
ENTRY:: November 02, 1995
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Finding Real-Valued Single-Source Shortest Paths in o(n^3) Expected Time
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Kolliopoulos, Stavros G.
AUTHOR:: Stein, Clifford
DATE:: October 1995
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.
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR95-272.pdf
END::