A practical Single Source Shortest Path algorithm for random directed graphs with arbitrary weight in expecting linear time

Dexin Li

In this paper, I present an algorithm called Raffica algorithm for Single-Source Shortest Path(SSSP). On random graph, this algorithm has linear time complexity(in expect). More pr…