We propose a new parallel algorithm for the single-source shortest-path problem (SSSP). Its heap data structure is particularly advantageous on graphs with a moderate number of high degree nodes. On arbitrary directed graphs with n nodes, m edges and independent random edge weights uniformly distributed in the range [0, 1] and maximum shortest path weight L the PRAM version of our algorithm runs in O(log~2 n·min_i{2~i·L·log n + |V_i|}) average-case time using O(n·log n + m) operations where |V_i| is the number of graph vertices with degree at least 2~i. For power-law graph models of the Internet or call graphs this results in the first work-efficient o(n~(1/4)) average-case time algorithm.
展开▼
机译：我们为单源最短路径问题（SSSP）提出了一种新的并行算法。其堆数据结构在具有适度数量的高度节点的图表上特别有利。在具有N个节点的任意定向图中，M边缘和独立随机边缘权重均匀分布在[0,1]和最大的最短路径重量l中，我们的算法的PRAM版本在O（log〜2 n·min_i {2〜 i·lablog n + | v_i |}）使用O（n·log n + m）操作的平均案例时间| V_I |是具有至少2〜i度的图形顶点的数量。对于互联网的电源 - 法律图模型或呼叫图，这导致第一工作高效的O（n〜（1/4））平均案例时间算法。
展开▼
