寻找第k条最短路径?

发布于 2024-12-01 12:24:17 字数 538 浏览 1 评论 0原文

寻找图中两点之间的最短路径是一个经典的算法问题,有很多很好的答案(Dijkstra 算法< /a>, Bellman-Ford 等)我的问题是是否存在一种有效的算法,给定一个有向加权图、一对节点 s 和 t 以及一个值 k,找到s 和 t 之间的第 k 最短路径。如果有多条长度相同的路径都与第 k 最短路径相关,则算法可以返回其中任何一条路径。

我怀疑这个算法可能可以在多项式时间内完成,尽管我知道可能会减少 最长路径问题,这将使它成为NP难题。

有谁知道这样的算法,或者知道它是 NP 困难的简化算法吗?

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.

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.

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

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(4

一紙繁鸢 2024-12-08 12:24:17

您正在寻找 Yen 的算法来查找 K 最短路径。第 k 个最短路径将成为该组中的最后一条路径。

以下是 Yen 算法的实现

这是描述它的原始论文

You're looking for Yen's algorithm for finding K shortest paths. The kth shortest path will then be the last path in that set.

Here's an implementation of Yen's algorithm.

And here's the original paper describing it.

习惯成性 2024-12-08 12:24:17

最好的(基本上是最佳的)算法是由于 艾普斯坦

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

兮子 2024-12-08 12:24:17

从可用的第 K 个最短路径算法中,Yen 的算法是最容易理解的。这主要是因为Yen的算法首先需要计算所有K-1条最短路径,然后才能计算第K条最短路径,因此它可以分解为子问题。

此外,由于每个子问题都使用标准的最短路径算法(例如Dijkstra算法),它是从第一个最短路径问题到第K个最短路径问题的更自然的延伸。

以下是在具有等权边的示例图中查找第三条最短路径的工作原理。

第一条最短路径 (K=1)

如果我们正在寻找起点和目的地之间的第一条最短路径(此处为 DF),我们可以运行 Dijkstra 算法。 Yen 算法在第一次迭代时的完整代码是:

shortest_1 = Dijkstra(graph, D, F)

给定一个起始图,这给出了第一个最短路径(K=1)。

第一条最短路径

第二条最短路径 (K=2)

寻找第二条最短路径的直觉是采用第一条最短路径,但“强制”Dijkstra 算法沿着不同的、稍微不同的方向前进。不太理想的路线。 Yen 的算法“迫使”Dijkstra 的算法沿着不同的路线行驶的方式是删除属于第一条最短路径的边之一。

但是我们要删除哪条边才能得到下一条最短路径呢?我们需要尝试一条一条地删除每条边,看看删除哪一条边可以为我们提供下一条最短路径。

第二条最短路径

首先,我们尝试删除边 DEshortest_1 中的第一条边),然后通过运行 Dijkstra(graph_1, D、 F)。我们将已知的从节点 DD(这只是节点 D 本身)的最短路径与从节点开始的新最短路径结合起来DF。这为我们提供了一条替代路径D->F

然后我们尝试删除边 EFshortest_1 中的第二条边),然后通过运行 Dijkstra(graph_2, E, F)< 来完成最短路径/代码>。我们将已知的从节点 DE 的最短路径与从节点 EF 的新最短路径结合起来>。这为我们提供了另一条替代路径D->F

因此,第二次迭代的过程如下所示:

// Try without edge 1
graph_1 = remove_edge(graph, D-E)
candidate_1 = shortest_1(D, D) + Dijkstra(graph_1, D, F)

// Try without edge 2
graph_2 = remove_edge(graph, E-F)
candidate_2 = shortest_1(D, E) + Dijkstra(graph_2, E, F)

shortest_2 = pick_shortest(candidate_1, candidate_2)

最后,选择替代新路径中最短的一条作为第二最短路径。

第三条最短路径(K=3)

正如通过从第一条最短路径中删除边来找到第二条最短路径一样,第三条最短路径也是通过从第二条最短路径中删除边来找到第三条最短路径。

不过,这次新的细微差别是,当我们删除边 DAshortest_2 中的第一条边)时,我们还想删除边 DE.如果我们不这样做,而只删除边DA,那么当我们在graph_3上运行Dijkstra时,我们将再次找到第一条最短路径(DEF),而不是第三条最短路径!

但是,对于 graph_4graph_5,我们不需要删除任何其他边,因为这些边在使用时不会为我们提供之前看到的最短路径。

,整个过程看起来与查找第二条最短路径类似,但细微之处在于,除了第二条最短路径之外,我们还希望删除在第一条最短路径中看到的一些边。该决定是根据 shortest_1shortest_2 是否共享通向要删除的边的子路径来做出的。

// Try without edge 1
edges_3 = [D-A]
if shortest_1 and shortest_2 share subpath up to node D: 
    // True because both shortest_1 and shortest_2 have D in shortest path
    // D-E is edge in shortest_1 that is connected from D, and so it is added
    edges_3.add(D-E)

graph_3 = remove_edges(graph, edges_3)
candidate_3 = shortest_e(D, D) + Dijkstra(graph_3, D, F) // returns infinity


// Try without edge 2
edges_4 = [A-E]
if shortest_1 and shortest_2 share subpath up to node A:
    // False because there are no edges in shortest_1 that go through A
    // So no edges added

graph_4 = remove_edges(graph, edges_4)
candidate_4 = shortest_2(D, A) + Dijkstra(graph_4, A, F) // returns infinity


// Try without edge 3
edges_5 = [E-F]
if shortest_1 and shortest_2 share subpath up to node E:
    // False because shortest_1 goes through D-E while shortest_2 goes through D-A-E
    // So no edges added

graph_5 = remove_edges(graph, edges_5)
candidate_5 = shortest_2(D, E) + Dijkstra(graph_5, E, F)


shortest_3 = pick_shortest(candidate_2, candidate_3, candidate_4, candidate_5)

请注意,当我们这次选择最短路径时,我们考虑了迭代 2 中未使用的候选路径(即 candidate_2),并且实际上最终选择了从 graph_2 中找到的最短路径。同样的,在下一次迭代(K=4)时,我们会发现第4条最短路径实际上是在迭代K=3时找到的。可以看到,这个算法是提前做工作的,所以它在寻找第K条最短路径的同时,也在探索第K条最短路径之外的一些路径。因此,它不是解决第 K 最短路径问题的最优算法。 Eppstein算法可以做得更好,但更复杂。

上述方法可以通过使用多个嵌套循环来推广。 关于 Yen 算法的维基百科页面 已经为更通用的实现提供了出色的伪代码,所以我将不要写在这里。请注意,维基百科代码使用列表 A 来保存每个最短路径,使用列表 B 来保存每个候选路径,并且候选最短路径在循环迭代中持续存在。

备注

由于使用了Dijkstra算法,Yen算法不可能有第K条包含环路的最短路径。当使用未加权的边时(如上例所示),这种情况并不那么明显,但如果添加权重,则可能会发生这种情况。因此,Eppstein 的算法也效果更好,因为它考虑了循环。 此其他答案包括 链接,对 Eppstein 算法进行了很好的解释。

From the available Kth shortest path algorithms, Yen’s algorithm is the easiest to understand. Mostly this is because Yen’s algorithm first needs to compute all K-1 shortest paths before it can compute the Kth shortest path, so it can be broken down into sub-problems.

Furthermore, since each sub-problem uses a standard shortest path algorithm (e.g. Dijkstra’s algorithm), it is a more natural extension from the 1st shortest path problem to the Kth shortest path problem.

Here is how it works for finding the 3rd shortest path in an example graph with equal-weight edges.

1st shortest path (K=1)

If we are looking for the 1st shortest path between a start and a destination (here, between D and F), we can just run Dijkstra’s algorithm. The entire code for Yen’s algorithm at the first iteration is:

shortest_1 = Dijkstra(graph, D, F)

Given a starting graph, this gives the 1st shortest path (K=1).

First shortest path

2nd shortest path (K=2)

The intuition for finding the 2nd shortest path is to take the 1st shortest path but “force” Dijkstra’s algorithm along a different, slightly less optimal route. The way Yen’s algorithm “forces” Dijkstra’s algorithm along a different route, is by removing one of the edges that are part of the 1st shortest path.

But which of the edges do we remove to get the next shortest path? We need to try removing each edge, one by one, and see which edge removal gives us the next shortest path.

Second shortest path

First we try to remove edge D-E (the first edge in shortest_1), and then complete the shortest path by running Dijkstra(graph_1, D, F). We combine the shortest path already known from node D to D (which is just the node D itself), with the new shortest path from node D to F. This gives us an alternative path D->F.

Then we try to remove the edge E-F (the second edge in shortest_1), and then complete the shortest path by running Dijkstra(graph_2, E, F). We combine the shortest path already known from node D to E, with the new shortest path from node E to F. This gives us yet another alternative path D->F.

The procedure for the 2nd iteration thus looks like this:

// Try without edge 1
graph_1 = remove_edge(graph, D-E)
candidate_1 = shortest_1(D, D) + Dijkstra(graph_1, D, F)

// Try without edge 2
graph_2 = remove_edge(graph, E-F)
candidate_2 = shortest_1(D, E) + Dijkstra(graph_2, E, F)

shortest_2 = pick_shortest(candidate_1, candidate_2)

At the end, the shortest of the alternative new paths is chosen as the 2nd shortest path.

3rd shortest path (K=3)

Just as the 2nd shortest path was found by removing edges from the 1st shortest path, the 3rd shortest path is found by removing edges from the 2nd shortest path.

The new nuance this time, however, is that for when we remove edge D-A (the first edge in shortest_2), we also want to remove edge D-E. If we don’t do this, and remove only the edge D-A, then when we run Dijkstra on graph_3, we will find the 1st shortest path again (D-E-F), instead of the 3rd shortest path!

For graph_4 and graph_5, however, we do not need to remove any other edges, since those edges, when used, won’t give us previously seen shortest paths.

Third shortest path

Thus, the overall procedure looks similar to finding the 2nd shortest path, but with the nuance that we also want to remove some edges seen in the 1st shortest path in addition to the 2nd shortest path. The decision is made based on whether shortest_1 and shortest_2 share a subpath leading up to the edge which is being removed.

// Try without edge 1
edges_3 = [D-A]
if shortest_1 and shortest_2 share subpath up to node D: 
    // True because both shortest_1 and shortest_2 have D in shortest path
    // D-E is edge in shortest_1 that is connected from D, and so it is added
    edges_3.add(D-E)

graph_3 = remove_edges(graph, edges_3)
candidate_3 = shortest_e(D, D) + Dijkstra(graph_3, D, F) // returns infinity


// Try without edge 2
edges_4 = [A-E]
if shortest_1 and shortest_2 share subpath up to node A:
    // False because there are no edges in shortest_1 that go through A
    // So no edges added

graph_4 = remove_edges(graph, edges_4)
candidate_4 = shortest_2(D, A) + Dijkstra(graph_4, A, F) // returns infinity


// Try without edge 3
edges_5 = [E-F]
if shortest_1 and shortest_2 share subpath up to node E:
    // False because shortest_1 goes through D-E while shortest_2 goes through D-A-E
    // So no edges added

graph_5 = remove_edges(graph, edges_5)
candidate_5 = shortest_2(D, E) + Dijkstra(graph_5, E, F)


shortest_3 = pick_shortest(candidate_2, candidate_3, candidate_4, candidate_5)

Note how when we pick the shortest path this time, we take into account unused candidates from iteration 2 (i.e. candidate_2), and actually end up picking the shortest path found from graph_2. In the same way, on the next iteration (K=4), we will find that the 4th shortest path was actually found in iteration K=3. As you can see, this algorithm is doing work in advance, so while it is finding the Kth shortest path, it is also exploring some of the paths beyond the Kth shortest path. It is thus not the most optimal algorithm for the Kth shortest path problem. The Eppstein algorithm can do better, but it is more complex.

The above approach can be generalized by using several nested loops. The Wikipedia page on Yen’s algorithm already gives excellent pseudocode for the more generic implementation, so I will refrain from writing it here. Note that the Wikipedia code uses a list A to hold each shortest path, and a list B to hold each candidate path, and that candidate shortest paths persist across loop iterations.

Remarks

Due to the use of Dijkstra’s algorithm, Yen’s algorithm cannot have a Kth shortest path that contains a loop. This is not as noticable when un-weighted edges are used (as in the example above), but could occur if weights are added. For this reason, Eppstein’s algorithm works better as well, since it considers loops. This other answer includes a link to a good explanation of Eppstein’s algorithm.

猫九 2024-12-08 12:24:17

尽管该问题有一个有效的可接受答案,但该答案通过提供示例工作代码解决了实现问题。在这里找到第 k 个最短路径的有效代码:

// 时间复杂度:O(Vk(V*logV + E))

using namespace std;

typedef long long int ll;
typedef short int i16;
typedef unsigned long long int u64;
typedef unsigned int u32;
typedef unsigned short int u16;
typedef unsigned char u8;

const int N = 128;

struct edge
{
    int to,w;
    edge(){}
    edge(int a, int b)
    {
        to=a;
        w=b;
    }
};

struct el
{
    int vertex,cost;
    el(){}
    el(int a, int b)
    {
        vertex=a;
        cost=b;
    }
    bool operator<(const el &a) const
    {
        return cost>a.cost;
    }
};

priority_queue <el> pq;

vector <edge> v[N];

vector <int> dist[N];

int n,m,q;

void input()
{
    int i,a,b,c;
    for(i=0;i<N;i++)
        v[i].clear();
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d", &a, &b, &c);
        a++;
        b++;
        v[a].push_back(edge(b,c));
        v[b].push_back(edge(a,c));
    }
}

void Dijkstra(int starting_node, int ending_node)
{
    int i,current_distance;
    el curr;
    for(i=0;i<N;i++)
        dist[i].clear();
    while(!pq.empty())
        pq.pop();
    pq.push(el(starting_node,0));
    while(!pq.empty())
    {
        curr=pq.top();
        pq.pop();
        if(dist[curr.vertex].size()==0)
            dist[curr.vertex].push_back(curr.cost);
        else if(dist[curr.vertex].back()!=curr.cost)
            dist[curr.vertex].push_back(curr.cost);
        if(dist[curr.vertex].size()>2)
            continue;
        for(i=0;i<v[curr.vertex].size();i++)
        {
            if(dist[v[curr.vertex][i].to].size()==2)
                continue;
            current_distance=v[curr.vertex][i].w+curr.cost;
            pq.push(el(v[curr.vertex][i].to,current_distance));
        }
    }
    if(dist[ending_node].size()<2)
        printf("?\n");
    else
        printf("%d\n", dist[ending_node][1]);
}

void solve()
{
    int i,a,b;
    scanf("%d", &q);
    for(i=1;i<=q;i++)
    {
        scanf("%d %d", &a, &b);
        a++;
        b++;
        Dijkstra(a,b);
    }
}

int main()
{
    int i;
    for(i=1;scanf("%d %d", &n, &m)!=EOF;i++)
    {
        input();
        printf("Set #%d\n", i);
        solve();
    }
    return 0;
}

Even though, the question has a valid accepted answer, this answer addresses the problem of implementation by providing a sample working code. Find the valid code for kth shortest path here:

// Time complexity: O(Vk(V*logV + E))

using namespace std;

typedef long long int ll;
typedef short int i16;
typedef unsigned long long int u64;
typedef unsigned int u32;
typedef unsigned short int u16;
typedef unsigned char u8;

const int N = 128;

struct edge
{
    int to,w;
    edge(){}
    edge(int a, int b)
    {
        to=a;
        w=b;
    }
};

struct el
{
    int vertex,cost;
    el(){}
    el(int a, int b)
    {
        vertex=a;
        cost=b;
    }
    bool operator<(const el &a) const
    {
        return cost>a.cost;
    }
};

priority_queue <el> pq;

vector <edge> v[N];

vector <int> dist[N];

int n,m,q;

void input()
{
    int i,a,b,c;
    for(i=0;i<N;i++)
        v[i].clear();
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d", &a, &b, &c);
        a++;
        b++;
        v[a].push_back(edge(b,c));
        v[b].push_back(edge(a,c));
    }
}

void Dijkstra(int starting_node, int ending_node)
{
    int i,current_distance;
    el curr;
    for(i=0;i<N;i++)
        dist[i].clear();
    while(!pq.empty())
        pq.pop();
    pq.push(el(starting_node,0));
    while(!pq.empty())
    {
        curr=pq.top();
        pq.pop();
        if(dist[curr.vertex].size()==0)
            dist[curr.vertex].push_back(curr.cost);
        else if(dist[curr.vertex].back()!=curr.cost)
            dist[curr.vertex].push_back(curr.cost);
        if(dist[curr.vertex].size()>2)
            continue;
        for(i=0;i<v[curr.vertex].size();i++)
        {
            if(dist[v[curr.vertex][i].to].size()==2)
                continue;
            current_distance=v[curr.vertex][i].w+curr.cost;
            pq.push(el(v[curr.vertex][i].to,current_distance));
        }
    }
    if(dist[ending_node].size()<2)
        printf("?\n");
    else
        printf("%d\n", dist[ending_node][1]);
}

void solve()
{
    int i,a,b;
    scanf("%d", &q);
    for(i=1;i<=q;i++)
    {
        scanf("%d %d", &a, &b);
        a++;
        b++;
        Dijkstra(a,b);
    }
}

int main()
{
    int i;
    for(i=1;scanf("%d %d", &n, &m)!=EOF;i++)
    {
        input();
        printf("Set #%d\n", i);
        solve();
    }
    return 0;
}
~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文