因此,我想这是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可能适合这一点。链接到英语文档很好,甚至是亚马逊上的书籍...

有帮助吗?

解决方案

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

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

在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

其他提示

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

许可以下: CC-BY-SA归因
不隶属于 StackOverflow
scroll top