Cómo almacenar un mapa y generar un gráfico con BFS en Ruby

Question

Así que supongo que esto es una pregunta clásica para alguien con MSC en el CS.

He elemento de N y tengo las distancias también. Digamos que tengo 3 elementos con las siguientes distancias. Es simétrica, por lo

A -> B == B -> A

Se ve como una matriz:

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

Mi pregunta sería:

• ¿cómo puedo guardar esto de manera eficiente (lo que la estructura de datos)
• ¿cuál es la forma más eficiente para obtener una lista enlazada, donde la suma de la distancia es mínima

En este caso es la mejor

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

otro caso:

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

Yo tenía la impresión de que BFS podría ser adecuado para esto. Enlace a la documentación en Inglés es bueno, incluso los libros en Amazon ...

Answer 1

The ideal solution for your data structure is an adjacency list.

An adjacency list is simply a list of objects (representing vertices on your graph). Each object has a list containing all the vertices that it has an adjacent edge to and the corresponding weight.

In ruby, a simple implementation might looking something like:

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

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

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

The algorithm to find the shortest, weighted path is called Dijkstra's.

If you would like to get the shortest path after running the algorithm, you can do a traceback. This is done by storing the (optimal) parent of each node as you reach it. In order to do this, you could have a hash for each visited node which maps to the node which lead to it with the least cost.

Once you have finished the algorithm, your recursive traceback may look something like this:

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

I hear Dijkstra has an algorithm to navigate a weighted graph.