b'@techreport{,'b'\nTITLE = {Directed single-source shortest-paths in linear average-case time},\nAUTHOR = {Meyer, Ulrich},\nLANGUAGE = {eng},\nURL = {http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2001-1-002},\nNUMBER = {MPI-I-2001-1-002},\nINSTITUTION = {Max-Planck-Institut f{\\"u}r Informatik},\nADDRESS = {Saarbr{\\"u}cken},\nYEAR = {2001},\nDATE = {2001},\nABSTRACT = {The quest for a linear-time single-source shortest-path (SSSP) algorithm on directed graphs with positive edge weights is an ongoing hot research topic. While Thorup recently found an ${\\cal O}(n+m)$ time RAM algorithm for undirected graphs with $n$ nodes, $m$ edges and integer edge weights in $\\{0,\\ldots, 2^w-1\\}$ where $w$ denotes the word length, the currently best time bound for directed sparse graphs on a RAM is ${\\cal O}(n+m \\cdot \\log\\log n)$. In the present paper we study the average-case complexity of SSSP. We give simple label-setting and label-correcting algorithms for arbitrary directed graphs with random real edge weights uniformly distributed in $\\left[0,1\\right]$ and show that they need linear time ${\\cal O}(n+m)$ with high probability. A variant of the label-correcting approach also supports parallelization. Furthermore, we propose a general method to construct graphs with random edge weights which incur large non-linear expected running times on many traditional shortest-path algorithms.},\nTYPE = {Research Report / Max-Planck-Institut f\xc3\xbcr Informatik},\n}\n'