3

所以我想这对于在 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 可能适合这个。英文文档的链接很好，即使是亚马逊上的书籍......

4

2 回答 2

4

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

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

在 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
于 2010-12-24T01:28:08.023 回答
-2

我听说Dijkstra有一个算法来导航加权图。

于 2010-12-22T23:27:18.913 回答