Trovare i k-percorsi più brevi?

Question

Trovare il percorso più breve tra due punti in un grafico è una classica domanda di algoritmi con molte buone risposte (Dijkstra's algorithm, Bellman-Ford, ecc.) La mia domanda è se esiste un algoritmo efficiente che, dato un grafico ponderato diretto, un paio di i nodi s e t, e un valore k, trova il cammino k-più breve tra s e t. Nel caso in cui ci siano più percorsi della stessa lunghezza che si legano tutti per il k-più corto, va bene che l'algoritmo restituisca ognuno di essi.

Ho il sospetto che questo algoritmo possa essere fatto in tempo polinomiale, anche se sono consapevole che potrebbe esserci una riduzione dallo longest path problem che lo renderebbe NP-hard.

Qualcuno sa di tale algoritmo o di una riduzione che mostra che è NP-difficile?

Answer 1

L'algoritmo migliore (e fondamentalmente ottimale) è dovuto a Eppstein.

Answer 2

Stai cercando l'algoritmo di Yen per trovare i percorsi più corti K. Il percorso più breve sarà quindi l'ultimo percorso in quella serie.

Ecco uno implementation dell'algoritmo di Yen.

Ed ecco il original paper che lo descrive.

Answer 3

Anche se la domanda ha una risposta valida accettata, questa risposta risolve il problema dell'implementazione fornendo un codice di esempio. Trovare il codice valido per KTH percorso più breve qui:

// Tempo complessità: 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; 
}