查找第k最短路径？ [英] Finding kth-shortest paths?

问题描述

查找两点之间的最短路径的图形与很多很好的答案（ Dijkstra算法 贝尔曼 - 福特等），我的问题是，是否有一个有效的算法是，给出一个指示，加权图中，一对节点s和t和的值k，认定s和t之间的第k-最短路径。倘若有相同的长度，所有并列第k-最短，它的优良的算法返回它们中的任何的多条路径。

Finding the shortest path between two points in a graph is a classic algorithms question with many good answers (Dijkstra's algorithm, Bellman-Ford, etc.) My question is whether there is an efficient algorithm that, given a directed, weighted graph, a pair of nodes s and t, and a value k, finds the kth-shortest path between s and t. In the event that there are multiple paths of the same length that all tie for the kth-shortest, it's fine for the algorithm to return any of them.

我怀疑这个算法大概可以在多项式时间内完成，但我知道，有可能是从最长减少路径问题这将使得NP难。

I suspect that this algorithm can probably be done in polynomial time, though I'm aware that there might be a reduction from the longest path problem that would make it NP-hard.

有谁知道这样的算法，即减少，显示这是一个NP难？

Does anyone know of such an algorithm, or of a reduction that show that it is NP-hard?

推荐答案

最好的（基本上优化）算法是由于<一个href="http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=7BB56B2ABC7C9113C121413A62AF3974?doi=10.1.1.30.3705&rep=rep1&type=pdf">Eppstein.

The best (and basically optimal) algorithm is due to Eppstein.

这篇关于查找第k最短路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！