Tìm đường dẫn k-ngắn nhất?

Question

Tìm đường đi ngắn nhất giữa hai điểm trong biểu đồ là câu hỏi thuật toán cổ điển với nhiều câu trả lời hay (Dijkstra's algorithm, Bellman-Ford, v.v.) Câu hỏi của tôi là liệu có một thuật toán hiệu quả, được chỉ định, biểu đồ có trọng số, một cặp các nút s và t, và một giá trị k, tìm đường k-ngắn nhất giữa s và t. Trong trường hợp có nhiều đường dẫn có cùng độ dài mà tất cả đều buộc cho kth-shortest, thì tốt nhất cho thuật toán trả về bất kỳ giá trị nào trong số chúng.

Tôi nghi ngờ rằng thuật toán này có thể có thể được thực hiện trong thời gian đa thức, mặc dù tôi biết rằng có thể có sự giảm từ longest path problem mà sẽ làm cho nó NP-cứng.

Có ai biết thuật toán như vậy hay giảm xuống cho thấy rằng đó là NP-hard không?

Answer 1

Thuật toán tốt nhất (và cơ bản tối ưu) là do Eppstein.

Answer 2

Bạn đang tìm thuật toán của Yen để tìm kiếm các đường đi ngắn nhất K. Con đường ngắn nhất k sau đó sẽ là con đường cuối cùng trong tập hợp đó.

Dưới đây là implementation thuật toán của Yen.

Và đây là số original paper mô tả.

Answer 3

Mặc dù câu hỏi có câu trả lời được chấp nhận hợp lệ, câu trả lời này giải quyết vấn đề triển khai bằng cách cung cấp mã làm việc mẫu. Tìm mã có giá trị thứ k con đường ngắn nhất ở đây:

// Thời gian phức tạp: 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; 
}