如何存储地图并在Ruby中生成图形

Question

因此，我想这是CS中拥有MSC的人的经典问题。

我有N元素，也有距离。假设我有3个元素，以下距离。它是对称的，所以

A -> B == B -> A

看起来像一个矩阵：

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

我的问题是：

• 我如何有效地存储此（什么数据结构）
• 什么是获得最小距离之和最小的链接列表的最有效方法

在这种情况下，最好的是

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

其他情况：

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

我的印象是BFS可能适合这一点。链接到英语文档很好，甚至是亚马逊上的书籍...

Answer 1

数据结构的理想解决方案是 邻接列表.

邻接列表只是对象列表（表示图表上的顶点）。每个对象都有一个列表，其中包含其具有相邻边缘和相应权重的所有顶点。

在Ruby中，一个简单的实施可能看起来像：

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

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

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

找到最短的加权路径的算法称为 Dijkstra的.

如果您想在运行算法后获得最短路径，则可以进行追溯。这是通过在达到每个节点时存储每个节点的（最佳）父来完成的。为了做到这一点，您可以为每个访问的节点提供一个哈希，该节点映射到节点，而成本最低。

完成算法后，您的递归追溯可能看起来像这样：

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

我听见 Dijkstra 具有算法来导航加权图。