返回信息流最近有点时间，想着写一下网络中的算法，Dijkstra算法写出来之后，总觉得时间复杂度不太对。太高了。程序正确性，测试结果是对的，不过测试案例不多。求指教，如何写Dijkstra,或者这个算法如何改进，哪个地方多余了。在网上也学习了其他的实现，不过还是希望从自己的上进行改进。 @nuanyangyang
def dijkstra(graph,src):
length = len(graph)
type_ = type(graph)
if type_ == list:
nodes = [i for i in xrange(length)]
elif type_ == dict:
nodes = [i for i in graph.keys()]
visited = [src]
path = {src:{src:[]}}
nodes.remove(src)
distance_graph = {src:0}
pre = next = src
while nodes:
distance = float('inf')
for v in visited:
for d in nodes:
new_dist = graph[src][v] + graph[v][d]
if new_dist < distance:
distance = new_dist
next = d
pre = v
path[src][next] = [i for i in path[src][pre]]
path[src][next].append(next)
distance_graph[next] = distance
visited.append(next)
nodes.remove(next)
return distance_graph, path
if __name__ == '__main__':
graph_list = [ [0, 2, 1, 4, 5, 1],
[1, 0, 4, 2, 3, 4],
[2, 1, 0, 1, 2, 4],
[3, 5, 2, 0, 3, 3],
[2, 4, 3, 4, 0, 1],
[3, 4, 7, 3, 1, 0]]
graph_dict = { "s1":{"s1": 0, "s2": 2, "s10": 1, "s12": 4},
"s2":{"s1": 1, "s2": 0, "s10": 4, "s12": 2},
"s10":{"s1": 2, "s2": 1, "s10": 0, "s12":1},
"s12":{"s1": 3, "s2": 5, "s10": 2, "s12":0},
}
distance, path = dijkstra(graph_list, 2)
print distance, '\n', path
distance, path = dijkstra(graph_dict, 's2')
print distance, '\n', path
这是一条镜像帖。来源：北邮人论坛 / python / #7068同步于 2015/5/26
该镜像源已超过 30 天没有更新，可能在源站已被删除。
Python机器人发帖
Dijkstra 算法实现求指教
lc10210103
2015/5/26镜像同步8 回复
订阅后，新回复会通过你的通知中心匿名送达。
8 条回复
@nuanyangyang
http://www.ics.uci.edu/~eppstein/161/python/dijkstra.py
http://code.activestate.com/recipes/117228-priority-dictionary/?c=14991
以上两个链接我觉得有帮助。重点应该是在priority dictionary, 感觉他的D算法实现得有点诡异。
Python有priority queue，可以直接用。里面的元素是(dist, nodeid)二元组。这样比priority dict存储的元素数目多，但时间代价并不大。但如果图像你描述的那么稠密，那么瓶颈还是边的数目，再优化也得是O(n^2)的，只有当图比较稀疏的时候这种优化才有意义。
恩恩，我去google一下。另，我写的算法是不是复杂度过高了？
【 在 nuanyangyang 的大作中提到: 】
: Python有priority queue，可以直接用。里面的元素是(dist, nodeid)二元组。这样比priority dict存储的元素数目多，但时间代价并不大。但如果图像你描述的那么稠密，那么瓶颈还是边的数目，再优化也得是O(n^2)的，只有当图比较稀疏的时候这种优化才有意义。
三个循环，虽然只有最外面的跑了N次，里面是（1×(n-1)+2*(n-2)+..+(n-1)*1）= 没有到n^3，不过大于n^2.
【 在 nuanyangyang 的大作中提到: 】
:
: 有点。
我打印查看了一下链接中的算法，他最外层的for循环的 字典长度每一个循环都在变。没经过一个循环，就会加入新的探测出来的节点，而上一轮扫描的节点也被跳过了。所以两个for循环就可以把我最外层的while，三个循环一起跑完了。如何做到长度变化而不报错呢？只因为用了那个prioritydictionary？
经测试，他那个算法好像不太对。
graph_dict = { "s1":{"s1": 0, "s2": 2, "s10": 1, "s12": 4, "s5":3},
"s2":{"s1": 1, "s2": 0, "s10": 4, "s12": 2, "s5":2},
"s10":{"s1": 2, "s2": 1, "s10": 0, "s12":1, "s5":4},
"s12":{"s1": 3, "s2": 5, "s10": 2, "s12":0,"s5":1},
"s5":{"s1": 3, "s2": 5, "s10": 2, "s12":4,"s5":0},
}
从s1到s12应该是s1到s10，s10到s12，总共2. 而输出的路径却是s1->s12.
【 在 nuanyangyang 的大作中提到: 】
:
: 有点。