[Ruby] Recherche du plus court chemin avec l'algorithme de Dijkstra

[Sephi-Chan]

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 !

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

[Maks]

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)

[Sephi-Chan]

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.

[Maks]

Merci

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

[Argorate]

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

Imepc