Est-ce que quelqu'un connait l'algorithme pour trouver le chemin k-plus court, j'ai cherché sur Internet et trouvé le Yen mais c'est si complexe?Trouver le chemin K-plus court entre deux nœuds dans le graphique?
Merci beaucoup.
Il ne peut être fait efficacement (polynomiale) - le problème est NP-Hard
penser de cette façon - est que vous pourriez même trouver la longueur du chemin le plus court ak (asssume chemin simple ici) polynomiale, par faire une recherche binaire sur la plage [1,n!] pour k, vous pouvez trouver s'il y a un hamiltonian path dans le graphique (en trouvant un chemin de longueur n).
Comme le hamiltonian path problem est NP-Hard, il en va de même pour ce problème, et il n'y a pas de solution polynomiale connue.
(1) probablement, à moins P=NP, mais la plupart des chercheurs croient CS il est très peu probable
sr mais avez-vous un projet sur ce problème, je trouve que l'algorithme de yen est si long – NoCountry4OldMan
Au total, maintenant ...
Google pour l'algorithme de Djikstra. Il y a une implémentation here.
L'algorithme de Dijkstra trouve le chemin le plus court, pas le kième chemin le plus court. – amit
Pas de problème, mais le titre de votre question est ambigu. – Matt
ouais, Dij est pour le chemin le plus court ;-( – NoCountry4OldMan
Ceci est résolu avec l'ensemble de dissociation. Google, mais en un mot, vous avez 2 vecteurs. un pour les parents initialisé avec -1. l'autre pour le rang initialisé avec zéro. Commencez maintenant par le noeud source. vous allez pour chaque noeud possible, vous pouvez obtenir à partir de là. ajoutez-les à votre ensemble en faisant leur parent [i] = noeud actuel. La décision que l'on sera le parent de qui est fait en fonction du rang [i] qui détient le numéro
merci, je vais essayer ... – NoCountry4OldMan
Merci, pense que ce site est juste pour les gens qui savaient tout.Si nous le savions, nous n'allons jamais ici – NoCountry4OldMan
@ DzokerP Je comprends votre frustration, mais ce n'est pas un site pour les gens qui savent tout. Il s'agit cependant d'un site auquel des personnes répondent gratuitement dans notre temps libre. Si vous ne mettez pas beaucoup d'efforts dans une question, les autres ne passeront pas de temps sur une réponse. Essayez de lire les directives de Jon Skeet en posant une bonne question: http://msmvps.com/blogs/jon_skeet/archive/2010/08/29/writing-the-perfect-question.aspx – HaemEternal
Aussi, je ne pense pas que ce soit notre devoir de lui montrer comment fonctionne l'algorithme. Les algorithmes sont pleins de mathématiques, si il/elle n'est pas capable de comprendre, il/elle devrait apprendre la mathématique. Imho cette question n'a rien à voir avec SO et devrait être placée dans mathematica. En outre, «je trouve que l'algorithme de yen est si long» et «c'est tellement complexe» ne montre aucun effort pour comprendre l'algorithme, mais montre qu'il/elle ne veut tout simplement pas faire le travail. -1 – jAC