Linear time single

Is there an algorithm that solves the single-pair-shortest-path problem in linear time for mixed graphs (ie directed and undirected edges or undirected edges represented as two directed edges), with negative, real edge-weights and non-negative cycles ?

Wikipedia only mentions algorithms for the single-source and all-pairs variant of the problem. I know that these solving one of these problems also solves the single-pair problem, but none of them works in linear time and with all the above criterias.

So is there a linear time algorthm for the single-pair shortest path problem with all the above criterias?

---

No, there is not. Intuitively, no single-pair shortest-path algorithm which allows negative edge weights can be more asymptotically efficient than a single-source algorithm, since finding the shortest path to the goal may in the worst case involve finding shortest paths to each of some fixed proportion of the other nodes (in order to determine whether it's worth detouring to each one's negative-weight edges).

链接地址: http://www.djcxy.com/p/35256.html

上一篇: Kruskal算法的变化

下一篇: 线性时间单一