single-source shortest-paths on arbitrary directed graphs in linear average-case time
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 &Ogr; ( n + m ) time RAM algorithm for undirected graphs with n nodes, m edges and integer edge weights in {0,,2 w - 1} where w denotes the word length, the currently best time bound for directed sparse graphs on a RAM is &Ogr; ( n + m  log log n ). In the present paper we study the average-case complexity of SSSP. We give a simple algorithm for arbitrary directed graphs with random edge weights uniformly distributed in [0, 1] and show that it needs linear time &Ogr; ( n + m ) with high probability.
directed graph direct graph timing algorithm posit research log paper complexity randomization distributed probability case shortest path