找到第k个最短的路径？-Java 学习之路

找到图中两点之间的最短路径是一个经典的算法问题，有许多好的答案（Dijkstra's algorithm，Bellman-Ford等） . 我的问题是，在给定有向加权图的情况下，是否存在一个有效的算法，一对节点s和t，以及值k，找到s和t之间的第k个最短路径 . 如果有多条相同长度的路径都与第k个最短路径相关，那么算法返回任何路径都是正常的 .

我怀疑这个算法可能可以在多项式时间内完成，但我知道可能会减少longest path problem会使NP难以实现 .

有没有人知道这样的算法，或者表明它是NP难的减少？

4 回答

-1
根据可用的Kth最短路径算法，Yen的算法是最容易理解的 . 大多数情况下，这是因为Yen算法首先需要计算所有K-1最短路径才能计算出Kth最短路径，因此可以将其分解为子问题 .

此外，由于每个子问题使用标准的最短路径算法（例如Dijkstra’s algorithm），因此从第1个最短路径问题到第K个最短路径问题是更自然的扩展 .

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

1st shortest path (K=1)

如果我们正在寻找开始和目的地之间的第一条最短路径（这里，在 D 和 F 之间），我们可以运行Dijkstra的算法 . Yen算法在第一次迭代时的整个代码是：
```
shortest_1 = Dijkstra(graph, D, F)
```
给定起始图，这给出了第一个最短路径（K = 1） .

2nd shortest path (K=2)

找到第二条最短路径的直觉是采用第一条最短路径但是“强制”Dijkstra算法沿着不同的，略微不太理想的路径 . Yen的算法沿着不同的路径“强制”Dijkstra算法的方式是删除作为第一条最短路径的一部分的边缘之一 .

但是我们删除哪条边以获得下一条最短路径？我们需要尝试逐个删除每个边缘，并查看哪个边缘移除为我们提供了下一个最短路径 .

首先，我们尝试删除边 D-E （ shortest_1 中的第一个边），然后通过运行 Dijkstra(graph_1, D, F) 来完成最短路径 . 我们将节点 D 已知的最短路径与 D （它只是节点 D 本身）结合起来，使用从节点 D 到 F 的新最短路径 . 这为我们提供了另一条路径 D->F .

然后我们尝试删除边 E-F （ shortest_1 中的第二个边），然后通过运行 Dijkstra(graph_2, E, F) 来完成最短路径 . 我们将已知从节点 D 到 E 的最短路径与从节点 E 到 F 的新最短路径组合在一起 . 这为我们提供了另一种替代路径 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)
```
最后，选择最短的替代新路径作为第二最短路径 .

3rd shortest path (K=3)

正如通过从第1个最短路径移除边缘找到第2个最短路径一样，通过从第2个最短路径移除边缘来找到第3个最短路径 .

然而，这次的新细微差别在于当我们删除边 D-A （ shortest_2 中的第一个边）时，我们还想删除边 D-E . 如果我们不这样做，只删除边 D-A ，那么当我们在 graph_3 上运行Dijkstra时，我们将再次找到第一条最短路径（ D-E-F ），而不是第3条最短路径！

但是，对于 graph_4 和 graph_5 ，我们不需要删除任何其他边，因为这些边在使用时不会给我们以前看到的最短路径 .

因此，整个过程看起来类似于找到第二个最短路径，但是除了第二个最短路径之外，我们还希望去除在第一个最短路径中看到的一些边缘的细微差别 . 根据 shortest_1 和 shortest_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）中，我们将发现第四条最短路径实际上是在迭代K = 3中找到的 . 正如您所看到的，此算法正在提前工作，因此在找到第K个最短路径时，它也在探索Kth最短路径之外的一些路径 . 因此，它不是Kth最短路径问题的最优算法 . Eppstein算法可以做得更好，但它更复杂 .

通过使用几个嵌套循环可以推广上述方法 . Wikipedia page on Yen’s algorithm已经为更通用的实现提供了出色的伪代码，因此我将不再在此处编写它 . 请注意，维基百科代码使用列表 A 来保存每个最短路径，并使用列表 B 来保存每个候选路径，并且候选最短路径在循环迭代中持续存在 .

Remarks

由于使用了Dijkstra算法，Yen的算法不能具有包含循环的第K个最短路径 . 当使用未加权边缘时（如上例所示），这并不明显，但如果添加了权重，则可能发生这种情况 . 出于这个原因，Eppstein的算法效果也更好，因为它考虑了循环 . This other answer包含了对Eppstein算法的一个很好的解释 .
回复于 2024-04-29T21:11:43+08:00
10

最佳（并且基本上是最优的）算法归因于Eppstein .

回复于 2024-04-29T21:11:43+08:00
0

你_144139用于查找 K 最短路径的算法 . 然后，第_144141条最短路径将成为该组中的最后一条路径 .

这是Yen算法的implementation .

这是描述它的original paper .

回复于 2024-04-29T21:11:43+08:00

即使问题有一个有效的接受答案，这个答案通过提供样本工作代码来解决实现问题 . 在这里找到第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;
}

回复于 2024-04-29T21:11:43+08:00

找到第k个最短的路径？

4 回答

相关问题