Encontrar kth-shortest paths?

Question

Encontrar la ruta más corta entre dos puntos en un gráfico es una clásica pregunta de algoritmos con muchas buenas respuestas (Dijkstra's algorithm, Bellman-Ford, etc.) Mi pregunta es si hay un algoritmo eficiente que, dado un gráfico dirigido, ponderado, un par de los nodos s y t, y un valor k, encuentra la ruta k-shortest entre s y t. En el caso de que haya varias rutas de la misma longitud que todas las vinculadas para la k-más corta, está bien que el algoritmo devuelva cualquiera de ellas.

Sospecho que este algoritmo probablemente se puede hacer en tiempo polinomial, aunque soy consciente de que podría haber una reducción desde el longest path problem que lo haría NP-duro.

¿Alguien sabe de tal algoritmo, o de una reducción que muestre que es NP-hard?

Answer 1

El mejor (y básicamente óptimo) algoritmo se debe a Eppstein.

Answer 2

Está buscando el algoritmo de Yen para encontrar K rutas más cortas. La ruta más corta k será la última ruta en ese conjunto.

Aquí hay un implementation del algoritmo de Yen.

Y aquí está el original paper describiéndolo.

Answer 3

Aunque la pregunta tiene una respuesta válida aceptada, esta respuesta resuelve el problema de la implementación al proporcionar un código de trabajo de muestra. Encontrar el código válido para la k-ésima trayectoria más corta aquí:

// Complejidad de tiempo: 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; 
}