We study the average-case running-time of single-source shortest-path (SSSP) algorithms assuming arbitrary directed graphs with n nodes, m edges, and independent random edge weights uniformly distributed in [0, 1]. We give the first label-setting and label-correcting algorithms that run in linear time 0(n + m) on the average. In fact, the result for the label-setting version is even obtained for dependent edge weights. In case of independence, however, the linear-time bound holds with high probability, too.Furthermore, we propose a general method to construct graphs with random edge weights that cause large expected running times when input to many traditional SSSP algorithms. We use our method to prove lower bounds on the average-case complexity of the following algorithms: the "Bellman-Ford algorithm" [R. Bellman, Quart. Appl. Math. 16 (1958) 87-90, L.R. Ford, D.R. Fulkerson, 1963], "Pallottino's Incremental Graph algorithm" [S. Pallottino, Networks 14 (1984) 257-267], the "Threshold approach" [F. Glover, R. Glover, D. Klingman, Networks 14 (1984) 23-37, F. Glover, D. Klingman, N. Phillips, Oper. Res. 33 (1985) 65-73, F. Glover, D. Klingman, N. Phillips, R.F. Schneider, Management Sci. 31 (1985) 1106-1128], the "Topological Ordering SSSP algorithm" [A.V. Goldberg, T. Radzik, Appl. Math. Lett. 6 (1993) 3-6], the "Approximate Bucket implementation" of Dijkstra's algorithm [B.V. Cherkassky, A.V. Goldberg, T. Radzik, Math. Programming 73 (1996) 129-174], and the "Delta-Stepping algorithm" [U. Meyer, P. Sanders, 1998]. (C) 2003 Elsevier Inc. All rights reserved.
展开▼
