JeuWeb - Crée ton jeu par navigateur
[Ruby] Recherche du plus court chemin avec l'algorithme de Dijkstra - Version imprimable

+- JeuWeb - Crée ton jeu par navigateur (https://jeuweb.org)
+-- Forum : Discussions, Aide, Ressources... (https://jeuweb.org/forumdisplay.php?fid=38)
+--- Forum : Programmation, infrastructure (https://jeuweb.org/forumdisplay.php?fid=51)
+--- Sujet : [Ruby] Recherche du plus court chemin avec l'algorithme de Dijkstra (/showthread.php?tid=6529)

[Ruby] Recherche du plus court chemin avec l'algorithme de Dijkstra - Sephi-Chan - 21-12-2012

Hello,

Dans le cadre du développement de Seelies, j'ai implémenté l'algorithme de Dijkstra en Ruby.

Vous trouverez un exemple d'utilisation dans le fichier de test (effectué avec le graphe proposé dans cet article).



graph       = Graph.new

arras       = Node.new('Arras')

bordeaux    = Node.new('Bordeaux')

brest       = Node.new('Brest')

lyon        = Node.new('Lyon')

marseille   = Node.new('Marseille')

montpellier = Node.new('Montpellier')

nantes      = Node.new('Nantes')

paris       = Node.new('Paris')

poitiers    = Node.new('Poitiers')

strasbourg  = Node.new('Strasbourg')



graph.add_edge(arras, strasbourg, 522)

graph.add_edge(arras, paris, 185)

graph.add_edge(arras, nantes, 561)



graph.add_edge(bordeaux, nantes, 334)

graph.add_edge(bordeaux, poitiers, 237)



graph.add_edge(brest, nantes, 298)

graph.add_edge(brest, paris, 593)



graph.add_edge(lyon, paris, 465)

graph.add_edge(lyon, strasbourg, 494)

graph.add_edge(lyon, marseille, 315)

graph.add_edge(lyon, montpellier, 303)



graph.add_edge(marseille, strasbourg, 809)

graph.add_edge(marseille, lyon, 315)

graph.add_edge(marseille, montpellier, 171)



graph.add_edge(montpellier, poitiers, 557)

graph.add_edge(montpellier, lyon, 303)

graph.add_edge(montpellier, strasbourg, 797)

graph.add_edge(montpellier, marseille, 171)



graph.add_edge(nantes, arras, 561)

graph.add_edge(nantes, paris, 386)

graph.add_edge(nantes, bordeaux, 334)

graph.add_edge(nantes, brest, 298)



graph.add_edge(paris, brest, 593)

graph.add_edge(paris, nantes, 386)

graph.add_edge(paris, arras, 185)

graph.add_edge(paris, lyon, 465)

graph.add_edge(paris, poitiers, 338)



graph.add_edge(poitiers, paris, 338)

graph.add_edge(poitiers, montpellier, 557)

graph.add_edge(poitiers, bordeaux, 237)



graph.add_edge(strasbourg, arras, 522)

graph.add_edge(strasbourg, lyon, 494)

graph.add_edge(strasbourg, montpellier, 797)

graph.add_edge(strasbourg, marseille, 809)



path = graph.shortest_path(bordeaux, strasbourg)



assert_equal [ bordeaux, poitiers, paris, arras, strasbourg ], path.nodes

assert_equal 1282, path.distance

De nombreuses implémentation sont disponibles à travers le Web, mais la plupart affichent — à mon grand regret — des noms de variables minimalistes qui donnent l'impression d'avoir affaire à du code obfusqué. En voici donc une avec des noms intelligibles ! Smile

J'espère qu'elle pourra vous être utile (peut-être pour vous aider à l'implémenter dans votre langage de prédilection) !

RE: [Ruby] Recherche du plus court chemin avec l'algorithme de Dijkstra - Maks - 22-12-2012

Ma question n'a pas grand chose à voir mais je me suis toujours demandé ce que faisait l'opérateur << en Ruby ?

@nodes << node unless @nodes.include?(node)


RE: [Ruby] Recherche du plus court chemin avec l'algorithme de Dijkstra - Sephi-Chan - 22-12-2012

La méthode << est disponible sur les instances de la classe Array. Elle permet d'ajouter un élément à la fin du tableau et de retourner le tableau. À la différence de la méthode push, elle n'accepte qu'un argument.

RE: [Ruby] Recherche du plus court chemin avec l'algorithme de Dijkstra - Maks - 22-12-2012

Merci Smile

Bonne idée chez Ruby de retourner le tableau lui-même plutôt que la longueur comme en Javascript.

RE: [Ruby] Recherche du plus court chemin avec l'algorithme de Dijkstra - Argorate - 22-12-2012

Excellent, ça me sera sans doute utile pour mon projet projet (en ruby) !

Imepc Wink