登入選單

返回Google圖書搜尋

Directed Single Source Shortest Paths in Linear Average Case Time

Ulrich Meyer

出版	MPI Informatik, Bibliothek & Dokumentation, 2001
URL	http://books.google.com.hk/books?id=-nFkGwAACAAJ&hl=&source=gbs_api

註釋

Abstract: "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 O(n + m) time RAM algorithm for undirected graphs with n nodes, m edges and integer edge weights in [0 ..., 2[superscript w]-1] where w denotes the word length, the currently best time bound for directed sparse graphs on a RAM is O(n + m · 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 [0,1] and show that they need linear time 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."