kth-shortest pathsを見つけるには？

Question

グラフ内の2点間の最短経路を見つけることは、古典的なアルゴリズムの問​​題です。多くの良い答えがあります（Dijkstra's algorithm、Bellman-Fordなど）。私の質問は、有向グラフ、ノードsとt、および値kは、sとtとの間のk番目に短いパスを見つける。同じ長さの複数のパスがすべてkth-shortestのすべての結び目である場合、アルゴリズムがそれらのどれかを返すことは問題ありません。

longest path problemからNP-hardになる可能性があることは分かっていますが、このアルゴリズムはおそらく多項式時間で実行できると思われます。

このようなアルゴリズム、またはそれがNP困難であることを示す削減を知っている人はいますか？

Answer 1

ベスト（と基本的に最適）アルゴリズムはEppsteinのためです。

Answer 2

Kの最短経路を見つけるための円のアルゴリズムを探しています。 k番目の最短パスは、そのセットの最後のパスになります。

ここではYenのアルゴリズムのimplementationです。

ここにはoriginal paperが記載されています。

Answer 3

質問には有効な回答がありますが、この回答はサンプルの作業コードを提供することで実装の問題に対処しています。ここで、k番目の最短経路のための有効なコードを探す：

//時間の複雑さ：O（V K（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; 
}