How to store a map and generate a graph with BFS in Ruby

Question

So I guess this is a classical question for somebody with MSC in CS.

I have N element and I have the distances as well. Let's say I have 3 elements with the following distances. It is symmetric, so

A -> B == B -> A

It looks like a matrix:

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

My question would be:

• how can I store this efficiently(what data structure)
• what is the most efficient way to get a linked list where the sum of distance is minimal

In this case the best is

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

other case:

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

I had the impression that BFS might be suitable for this. Link to documentation in English is good, even books on 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.