Dijkstra 算法概念和编码问题

Question

问题更新

我目前正在努力在 Python 中实现 Dijkstra 算法，我在这里查看了有关该算法的其他问题，但似乎没有一个适合我正在寻找的问题。

目前我的程序读取两个文本文件，其中一个包含网络路由图network.txt（基本上是路由成本）。

0,2,4,1,6,0,0
2,0,0,0,5,0,0
4,0,0,0,0,5,0
1,0,0,0,1,1,0
6,5,0,1,0,5,5
0,0,5,1,5,0,0
0,0,0,0,5,0,0

以及包含所需路由 (route.txt) 的

B>F

网络路由表： （每条线都是一个节点及其链接，因此节点 A 链接到 B、C、D 和 E）

      A  B  C  D  E  F  G

A    [0, 2, 4, 1, 6, 0, 0]
B    [2, 0, 0, 0, 5, 0, 0]
C    [4, 0, 0, 0, 0, 5, 0]
D    [1, 0, 0, 0, 1, 1, 0]
E    [6, 5, 0, 1, 0, 5, 5]
F    [0, 0, 5, 1, 5, 0, 0]
G    [0, 0, 0, 0, 5, 0, 0]

网络上的节点： ([Structure] PreviousNode, DistanceFromSource, Visited)

A    [-1, 1000000000, False]
B    [-1, 1000000000, False]
C    [-1, 1000000000, False]
D    [-1, 1000000000, False]
E    [-1, 1000000000, False]
F    [-1, 1000000000, False]
G    [-1, 1000000000, False]

我有点理解 Dijkstra 算法，但是使用我拥有的两种数据结构，再加上必须用 Python 编写它，我不知道从这里去哪里，因为我无法在不懂语言的情况下，我要弄清楚如何做到这一点。

我有一些非常基本的“伪代码”来说明我下一步需要做什么

• 3 - 检查当前节点的所有未访问的邻居并计算 它们距起始节点的暂定距离，覆盖 如果新值较低，则现有距离

• 4 - 将当前节点标记为已访问（不会再次检查）

• 5 - 如果不在目的地且存在未访问节点，则转到最小> 的未访问节点。距初始节点的距离，使其成为当前节点，否则结束

• 6 - 返回 3

有谁能够帮助我将“伪代码”翻译成代码或者更有意义的伪代码会很棒，因为我正在努力解决这个问题

Answer 1

在对象之间使用本机 python“链接”，例如：

edges = {1: set([2,3,4]), 2: set([1,5]), ....}
costs = {(1, 2): 99.3, (1, 3): 127.77, ...}

无需为如此简单的问题创建自己的类。

观看此内容以获取灵感：

http://python.mirocommunity.org/视频/1530/pycon-2010-mastering-team-play