Kième Shortest Path

Question

Est-ce que quelqu'un sait comment puis-je écrire un graphique algorithme de programmation (code de C serait génial) qui trouve le chemin le plus court Nième pour un ensemble de noeuds et des arêtes dans un graphe cyclique?

Par exemple, le chemin le plus court (qui pourrait être trouvé par Dijkstra ou Bellman Ford) est considéré comme le plus court chemin 1ème. Maintenant, le chemin le plus court 2ème est la plus courte qui vient après le 1er chemin le plus court. Maintenant, je veux l'algorithme pour trouver le chemin du Nième. vous donne le nombre de noeuds, les arêtes et l'ensemble des arêtes, comme suit:

nombre de noeuds

: 5
nombre d'arêtes: 6
bords:
0 1
0 2
1 2
2 3
3 1
1 4
nœud source: 0
noeud de destination: 4

« Notez que ce graphique contient un cycle » Merci.

Answer 1

Utilisez un coût uniforme algorithme recherche . Lorsque la Wikipédia dit « solution de retour », ne quittez pas et return mais ajouter le résultat à une liste jusqu'à ce que cette liste contient k chemins . Le k 'ième élément de la liste (comptage de 1) sera le k ' e chemin le plus court.

Ne pas garder un ensemble « fermé » / « explorer » ou cet algorithme ne fonctionnera pas correctement.