In this paper we present an O(W n~ω) time algorithm solving single source shortest path problem in graphs with integer weights from the set {—W,..., 0,..., W}, where ω < 2.376 is the matrix multiplication exponent. For dense graphs with small edge weights, this result improves upon the algorithm of Goldberg that works in O(mn~(0.5) log W) time, and the Bellman-Ford algorithm that works in O(nm) time.
展开▼
