Comment stocker une carte et générer un graphique avec BFS en Ruby

Question

Je suppose que cela est une question classique pour quelqu'un avec MSC dans CS.

J'ai élément N et j'ai les distances aussi bien. Disons que j'ai 3 éléments avec les distances suivantes. Il est symétrique, donc

A -> B == B -> A

Il ressemble à une matrice:

   A,  B,  C,  
A  0, 10,  20 
B 10,  0,  30
C 20, 30,   0

Ma question serait:

• comment puis-je conserver ce efficace (quelle structure de données)
• Quelle est la façon la plus efficace d'obtenir une liste chaînée la somme de la distance minimale est

Dans ce cas, le meilleur est

B -> A -> C = 30 which equals to C -> A -> B

autre cas:

A -> B -> C = 40 which equals to C -> B -> A

J'ai eu l'impression que BFS pourrait convenir à cet effet. Lien vers la documentation en anglais est bon, même des livres sur Amazon ...

Answer 1

La solution idéale pour votre structure de données est un liste de contiguïté .

Une liste de contiguïté est simplement une liste d'objets (représentant des sommets sur votre graphique). Chaque objet dispose d'une liste contenant tous les sommets qu 'il comporte un bord adjacent à et le poids correspondant.

En ruby, une implémentation simple pourrait regarder quelque chose comme:

vertices = {}
a = Vertex.new
b = Vertex.new

a.add(b, 10)
b.add(a, 10)

vertices[a] = a
vertices[b] = b

L'algorithme pour trouver le plus court, le chemin pondéré est appelé de href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm" Dijkstra.

Si vous souhaitez obtenir le chemin le plus court après l'exécution de l'algorithme, vous pouvez faire un retraçage. Cela se fait en stockant le parent (optimal) de chaque nœud que vous atteignez. Pour ce faire, vous pourriez avoir un hachage pour chaque noeud visité qui mappe au nœud qui y conduisent au moindre coût.

Une fois que vous avez terminé l'algorithme, votre retraçage récursive peut ressembler à ceci:

def traceback(parent, start, node, path)
  if(start == node)
     (path + start.to_s).reverse
  else
     path += node.to_s + " "
     traceback(parent, start, parent[node], path)
  end
end

Answer 2

J'entends Dijkstra a un algorithme pour naviguer dans un graphe pondéré.