Single-source shortest-paths on arbitrary directed graphs in linear average-case time.

Published in: SODA (2001)

Keyphrases

shortest path problem
single source
average case
directed graph
shortest path
worst case
random walk
directed acyclic graph
uniform distribution
maximum flow
shortest path algorithm
undirected graph
knn
markov chain