迪杰斯特拉算法概念与编码问题

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]

网络上的节点： （[结构] 上一个节点，距离起点的距离，是否已访问）

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/video/1530/pycon-2010-mastering-team-play