Come conservare una mappa e generare un grafico con BFS in Ruby

Question

Quindi credo che questa è una domanda classica per qualcuno con MSC in CS.

Ho elemento N e ho le distanze pure. Diciamo che ho 3 elementi con le seguenti distanze. E 'simmetrica, così

A -> B == B -> A

Si presenta come una matrice:

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

La mia domanda sarebbe:

• come posso conservare in modo efficiente (quale struttura dati)
• qual è il modo più efficace per ottenere una lista concatenata in cui la somma della distanza è minima

In questo caso il migliore è

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

altro caso:

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

Ho avuto l'impressione che BFS potrebbe essere adatto per questo. Link alla documentazione in inglese è buono, libri anche su 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.