1

在 Python 中，我有一个 Graph 类，它有一个顶点对象字典。每个顶点对象都有一个边字典（它由一个起始节点、结束节点和一个权重组成……想象一下箭头的末端指向另一个节点，并为其分配了一个旅行成本号）。

通过这些课程，我正在绘制 - 嗯，一个图表 - 飞机从一个城市飞到另一个城市所花费的时间。从这个图中，我应该使用 Dijkstra 算法确定两个节点之间的最短路径（最快路径）。我还应该确定从起始顶点可到达的所有顶点。

我能够在图表中完美地添加边和删除边（因此，添加节点）。然而，在我的一生中，我似乎无法找到一种简单的方法来使用我创建的数据结构来实现 Dijkstra 算法或广度优先搜索（以确定可达顶点）。

如果有人可以建议我需要做些什么来更改或实现这些算法以使其正常工作，我将非常感谢任何帮助。这是一个家庭作业，我已经做了将近一周，每天好几个小时，但我似乎无法通过这堵墙。再次，我将不胜感激任何建议或帮助。我不希望任何人为我编写代码，但伪代码会有所帮助（并且应用它——从维基百科复制和粘贴伪代码不会帮助我，因为我已经去过那里）。

4

1 回答 1

1

你的代码太复杂了。

从只实现基础的代码开始，然后逐渐添加功能。为了让您入门，我将在处理图表时发布一些简单但基本的内容。

from collections import deque

class fringe(object):
    def __init__(self, kind= 'stack'):
        f= deque()
        self._p= f.append if kind is 'stack' else f.appendleft
        self._f= f

    def __call__(self, item):
        self._p(item)
        return self

    def __iter__(self):
        while len(self._f):
            item= self._f.pop()
            yield item

    def __repr__(self):
        return self._f.__repr__().replace('deque', 'fringe')

def paths(G, start, terminal, F= fringe()):
    for node, path in F((start, [start])):
        for node in G[node]:
            if node is terminal:
                yield path+ [terminal]
            elif node not in path:
                F((node, path+ [node]))

和一个测试：

if __name__ == '__main__':
    a, b, c, d, e, f= 'A', 'B', 'C', 'D', 'E', 'F'
    G= {a: [b, c], b: [c, d], c: [d], d: [c], e: [f], f: [c]}
    print 'All paths from:', a, 'to:', d
    print 'BFS'
    for path in paths(G, a, d): print path
    print 'DFS'
    for path in paths(G, a, d, fringe('queue')): print path

运行将产生：

All paths from: A to: D
BFS
['A', 'C', 'D']
['A', 'B', 'D']
['A', 'B', 'C', 'D']
DFS
['A', 'B', 'D']
['A', 'C', 'D']
['A', 'B', 'C', 'D']
于 2011-05-11T10:13:37.810 回答