Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs

Ran Duan, Kaifeng Lyu, Hongxun Wu +1

In a directed graph $G=(V,E)$ with a capacity on every edge, a \emph{bottleneck path} (or \emph{widest path}) between two vertices is a path maximizing the minimum capacity of edge…