3

我应该如何继续这样做？这是一个家庭作业，我有一个很大的问题。现在，问题是我不能使用库。

我有一个像这样的图表：

{'A': {'C': 2, 'B': 10}, 'C': {'B': 7, 'D': 2}, 'B': {}, 'D': {'A': 5, 'B': 4}}

使用字典，取自文件。

我正在使用http://www.python.org/doc/essays/graphs/上的算法来查找所有路径，所以那里没有问题。

但是现在我有了从一个点到另一个点的所有路径，我需要对权重求和并得到它的全部成本。

如果你能帮助我，并指导我一些好的方法来接近它，我将不胜感激。

4

3 回答 3

2

看看networkx——这是一个非常好的 Python 图形库。阅读它的文档，你会发现有一个简单的解决方案——因为这是家庭作业，在你发现编码问题之前我不会发表更多评论。

于 2012-06-28T15:10:28.763 回答
1 
gr = {'A': {'C': 2, 'B': 10},
      'C': {'B': 7, 'D': 2},
      'B': {'E': 2},
      'D': {'A': 5, 'B': 4, 'E': 3}
      'E': {}}

def paths(gr, frm, to, path_len=0, visited=None):

    if frm == to:
        return [[to, path_len]]

    visited = visited or []
    result = []
    for point, length in gr[frm].iteritems():
        if point in visited:
            continue
        visited.append(point)
        for sub_path in paths(gr, point, to, path_len + length, visited[:]):
            result.append([frm] + sub_path)

    return result

>>> print paths(gr, 'A', 'E')
[['A', 'C', 'B', 'E', 11], ['A', 'C', 'D', 'E', 7], ['A', 'B', 'E', 12]]
于 2012-06-28T16:03:08.350 回答
0

好吧，你已经完成了寻找路径的艰难部分。现在只需通过路径并将这些权重相加。我会使用一个循环。

int sum=0;
for(int i=0;i<path.size()-1;i++)
    sum+= node.at(i).getWeightFor(node.at(i+1))

wheregetWeightFor(node)将返回从该节点到另一个节点的成本。因此，如果您这样做A.getWeightFor(C)，它将返回 2。可能有更好的方法可以做到这一点，但这是我的快速回答。您必须创建 getWeightFor 函数，但这应该很简单。就像我说的，困难的部分已经完成。最后一点不要想太多。

于 2012-06-28T14:52:47.137 回答