Trouver les chemins les plus courts?

Question

Trouver le plus court chemin entre deux points dans un graphique est une question d'algorithmes classique avec beaucoup de bonnes réponses (Dijkstra's algorithm, Bellman-Ford, etc.) Ma question est de savoir s'il existe un algorithme efficace qui, étant donné un graphique dirigé pondéré, les nœuds s et t, et une valeur k, trouvent le kième chemin le plus court entre s et t. Dans le cas où il y a plusieurs chemins de la même longueur que tous les liens pour le kth-shortest, il est bon pour l'algorithme de retourner l'un d'eux.

Je suppose que cet algorithme peut probablement être fait en temps polynomial, bien que je sache qu'il pourrait y avoir une réduction du longest path problem qui le rendrait NP-difficile.

Est-ce que quelqu'un connaît un tel algorithme, ou d'une réduction qui montre qu'il est NP-difficile?

Answer 1

Le meilleur algorithme (et fondamentalement optimal) est dû à Eppstein.

Answer 2

Vous recherchez l'algorithme de Yen pour trouver K chemins les plus courts. Le plus court chemin k sera alors le dernier chemin de cet ensemble.

Voici un implementation de l'algorithme de Yen.

Et voici le original paper le décrivant.

Answer 3

Même si la question a une réponse acceptée valide, cette réponse résout le problème de mise en œuvre en fournissant un exemple de code de travail. Trouvez le code valide pour kième chemin le plus court ici:

// complexité Temps: 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; 
}