python中的Dijkstra算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/22897209/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Dijkstra's algorithm in python
提问by user3504080
I am trying to implement Dijkstra's algorithm in python using arrays. This is my implementation.
我正在尝试使用数组在 python 中实现 Dijkstra 算法。这是我的实现。
def extract(Q, w):
m=0
minimum=w[0]
for i in range(len(w)):
if w[i]<minimum:
minimum=w[i]
m=i
return m, Q[m]
def dijkstra(G, s, t='B'):
Q=[s]
p={s:None}
w=[0]
d={}
for i in G:
d[i]=float('inf')
Q.append(i)
w.append(d[i])
d[s]=0
S=[]
n=len(Q)
while Q:
u=extract(Q,w)[1]
S.append(u)
#w.remove(extract(Q, d, w)[0])
Q.remove(u)
for v in G[u]:
if d[v]>=d[u]+G[u][v]:
d[v]=d[u]+G[u][v]
p[v]=u
return d, p
B='B'
A='A'
D='D'
G='G'
E='E'
C='C'
F='F'
G={B:{A:5, D:1, G:2}, A:{B:5, D:3, E:12, F:5}, D:{B:1, G:1, E:1, A:3}, G:{B:2, D:1, C:2}, C:{G:2, E:1, F:16}, E:{A:12, D:1, C:1, F:2}, F:{A:5, E:2, C:16}}
print "Assuming the start vertex to be B:"
print "Shortest distances", dijkstra(G, B)[0]
print "Parents", dijkstra(G, B)[1]
I expect the answer to be:
我希望答案是：
Assuming the start vertex to be B:
Shortest distances {'A': 4, 'C': 4, 'B': 0, 'E': 2, 'D': 1, 'G': 2, 'F': 4}
Parents {'A': 'D', 'C': 'G', 'B': None, 'E': 'D', 'D': 'B', 'G': 'D', 'F': 'E'}
However, the answer that I get is this:
然而，我得到的答案是这样的：
Assuming the start vertex to be B:
Shortest distances {'A': 4, 'C': 4, 'B': 0, 'E': 2, 'D': 1, 'G': 2, 'F': 10}
Parents {'A': 'D', 'C': 'G', 'B': None, 'E': 'D', 'D': 'B', 'G': 'D', 'F': 'A'}.
For the node F, the program gives the incorrect answer. Can someone please tell me why?
对于节点 F，程序给出了错误的答案。有人可以告诉我为什么吗？
回答by Hyperboreus
As others have pointed out, due to not using understandable variable names, it is almost impossible to debug your code.
正如其他人指出的那样，由于没有使用易于理解的变量名，几乎不可能调试您的代码。
Following the wiki article about Dijkstra's algorithm, one can implement it along these lines (and in a million other manners):
遵循关于 Dijkstra 算法的 wiki 文章，可以按照以下方式（以及其他一百万种方式）实现它：
nodes = ('A', 'B', 'C', 'D', 'E', 'F', 'G')
distances = {
'B': {'A': 5, 'D': 1, 'G': 2},
'A': {'B': 5, 'D': 3, 'E': 12, 'F' :5},
'D': {'B': 1, 'G': 1, 'E': 1, 'A': 3},
'G': {'B': 2, 'D': 1, 'C': 2},
'C': {'G': 2, 'E': 1, 'F': 16},
'E': {'A': 12, 'D': 1, 'C': 1, 'F': 2},
'F': {'A': 5, 'E': 2, 'C': 16}}
unvisited = {node: None for node in nodes} #using None as +inf
visited = {}
current = 'B'
currentDistance = 0
unvisited[current] = currentDistance
while True:
for neighbour, distance in distances[current].items():
if neighbour not in unvisited: continue
newDistance = currentDistance + distance
if unvisited[neighbour] is None or unvisited[neighbour] > newDistance:
unvisited[neighbour] = newDistance
visited[current] = currentDistance
del unvisited[current]
if not unvisited: break
candidates = [node for node in unvisited.items() if node[1]]
current, currentDistance = sorted(candidates, key = lambda x: x[1])[0]
print(visited)
This code is more verbous than necessary and I hope comparing your code with mine you might spot some differences.
这段代码比必要的更冗长，我希望将您的代码与我的代码进行比较，您可能会发现一些差异。
The result is:
结果是：
{'E': 2, 'D': 1, 'G': 2, 'F': 4, 'A': 4, 'C': 3, 'B': 0}
回答by docsnuz
This is not my answer - my prof did it much more efficiently than my attempt. Here is his approach, obviously using helper-functions for the repetitive tasks
这不是我的答案 - 我的教授比我的尝试更有效。这是他的方法，显然对重复性任务使用辅助函数
def dijkstra(graph, source):
vertices, edges = graph
dist = dict()
previous = dict()
for vertex in vertices:
dist[vertex] = float("inf")
previous[vertex] = None
dist[source] = 0
Q = set(vertices)
while len(Q) > 0:
u = minimum_distance(dist, Q)
print('Currently considering', u, 'with a distance of', dist[u])
Q.remove(u)
if dist[u] == float('inf'):
break
n = get_neighbours(graph, u)
for vertex in n:
alt = dist[u] + dist_between(graph, u, vertex)
if alt < dist[vertex]:
dist[vertex] = alt
previous[vertex] = u
return previous
Given a graph
给定一个图
({'A', 'B', 'C', 'D'}, {('A', 'B', 5), ('B', 'A', 5), ('B', 'C', 10), ('B', 'D', 6), ('C', 'D', 2), ('D', 'C', 2)})
({'A', 'B', 'C', 'D'}, {('A', 'B', 5), ('B', 'A', 5), ('B', ' C', 10), ('B', 'D', 6), ('C', 'D', 2), ('D', 'C', 2)})
the command print(dijkstra(graph, 'A')yields
命令print(dijkstra(graph, 'A')产生
Currently considering A with a distance of 0
Currently considering B with a distance of 5
Currently considering D with a distance of 11
Currently considering C with a distance of 13
当前考虑距离为 0 的 A
目前考虑距离为 5 的 B
目前考虑距离为 11 的 D
目前考虑距离为 13 的 C
id est:
身份验证：
{'C': 'D', 'D': 'B', 'A': None, 'B': 'A'} => in random order
{'C'：'D'，'D'：'B'，'A'：无，'B'：'A'} => 随机顺序
回答by Archibald
I wrote it in a more verbose form to make it clearer for a novice reader:
我用更详细的形式写了它，以使新手读者更清楚：
def get_parent(pos):
return (pos + 1) // 2 - 1
def get_children(pos):
right = (pos + 1) * 2
left = right - 1
return left, right
def swap(array, a, b):
array[a], array[b] = array[b], array[a]
class Heap:
def __init__(self):
self._array = []
def peek(self):
return self._array[0] if self._array else None
def _get_smallest_child(self, parent):
return min([
it
for it in get_children(parent)
if it < len(self._array)
], key=lambda it: self._array[it], default=-1)
def _sift_down(self):
parent = 0
smallest = self._get_smallest_child(parent)
while smallest != -1 and self._array[smallest] < self._array[parent]:
swap(self._array, smallest, parent)
parent, smallest = smallest, self._get_smallest_child(smallest)
def pop(self):
if not self._array:
return None
swap(self._array, 0, len(self._array) - 1)
node = self._array.pop()
self._sift_down()
return node
def _sift_up(self):
index = len(self._array) - 1
parent = get_parent(index)
while parent != -1 and self._array[index] < self._array[parent]:
swap(self._array, index, parent)
index, parent = parent, get_parent(parent)
def add(self, item):
self._array.append(item)
self._sift_up()
def __bool__(self):
return bool(self._array)
def backtrack(best_parents, start, end):
if end not in best_parents:
return None
cursor = end
path = [cursor]
while cursor in best_parents:
cursor = best_parents[cursor]
path.append(cursor)
if cursor == start:
return list(reversed(path))
return None
def dijkstra(weighted_graph, start, end):
"""
Calculate the shortest path for a directed weighted graph.
Node can be virtually any hashable datatype.
:param start: starting node
:param end: ending node
:param weighted_graph: {"node1": {"node2": weight, ...}, ...}
:return: ["START", ... nodes between ..., "END"] or None, if there is no
path
"""
distances = {i: float("inf") for i in weighted_graph}
best_parents = {i: None for i in weighted_graph}
to_visit = Heap()
to_visit.add((0, start))
distances[start] = 0
visited = set()
while to_visit:
src_distance, source = to_visit.pop()
if src_distance > distances[source]:
continue
if source == end:
break
visited.add(source)
for target, distance in weighted_graph[source].items():
if target in visited:
continue
new_dist = distances[source] + weighted_graph[source][target]
if distances[target] > new_dist:
distances[target] = new_dist
best_parents[target] = source
to_visit.add((new_dist, target))
return backtrack(best_parents, start, end)
回答by Kenny Ostrom
Set a breakpoint in extract. You will see that you delete entries from Q but never from w. Everything else is a dict, but Q/w are a paired array which you do not keep up to date. You have to keep those two in sync, or replace them with a dict. Special note: Eventually, after the algorithm is working, you may want to replace Q/w with a list of edges and re-code the "extract" function with a priority queue (heapq module).
在提取中设置断点。您将看到您从 Q 中删除条目，但从未从 w 中删除条目。其他一切都是字典，但 Q/w 是一个配对数组，您无法保持最新状态。你必须保持这两个同步，或者用字典替换它们。特别注意：最终，在算法工作后，您可能希望用边列表替换 Q/w，并使用优先级队列（heapq 模块）重新编码“提取”功能。
Additionally, you will see that w always has weights of 0 for the source, and 'inf' for all other nodes. You completely skipped the critical step where you update the candidate distances.
此外，您将看到 w 对于源的权重始终为 0，对于所有其他节点的权重为 'inf'。您完全跳过了更新候选距离的关键步骤。
So you are basically always taking the first path you encounter, rather than selecting the shortest path. You later compute the actual distance of that path, so the returned array of distances has actual values, but they were chosen arbitrarily, and you have no reason to expect them to be shortest.
所以你基本上总是走你遇到的第一条路径，而不是选择最短的路径。您稍后计算该路径的实际距离，因此返回的距离数组具有实际值，但它们是任意选择的，您没有理由期望它们是最短的。
After you (incorrectly) find the next node, you look at all of its edges. This should have been the critical step I mentioned above in the second paragraph, where you update the candidates for the next node. Instead you do something completely different: You appear to be looping through all the previous solutions (which are guaranteed correct and should be left alone, if you correctly implement dijkstra), and you look for a two-step solution from source->current->any. The correct intent for looking at those would have been to add the next candidate from previous paths to the next node, but because they never get added, you don't look at (previous shortest path) + (one step), you only look at literally two node solutions.
在您（错误地）找到下一个节点后，您会查看它的所有边。这应该是我上面在第二段中提到的关键步骤，您可以在其中更新下一个节点的候选者。相反，您做了一些完全不同的事情：您似乎在遍历所有以前的解决方案（保证正确，并且应该单独保留，如果您正确实施了 dijkstra），然后您从源代码->当前- > 任何。查看这些的正确意图是将先前路径中的下一个候选添加到下一个节点，但是因为它们从未被添加，所以您不会查看（先前最短路径）+（一步），您只查看在字面上的两个节点解决方案。
So basically, you are looping through all possible two-node paths from source in order to find the shortest paths. This is a complete error and has nothing to do with dijkstra. But it almost works on your tiny tiny graph where most of the correct shortest paths are two-step paths.
所以基本上，您是从源循环遍历所有可能的双节点路径以找到最短路径。这是一个完全错误，与dijkstra 无关。但它几乎适用于您的小图，其中大多数正确的最短路径都是两步路径。
(ps: I agree with everyone about your variable names. You would have done much better if you use verbose names telling what those variables represent. I had to rename them before I got anywhere analyzing your code.)
（ps：我同意每个人对你的变量名的看法。如果你使用详细的名字来告诉这些变量代表什么，你会做得更好。在我分析你的代码之前，我不得不重命名它们。）
回答by shadowroot
import sys
import heapq
class Node:
def __init__(self, name):
self.name = name
self.visited = False
self.adjacenciesList = []
self.predecessor = None
self.mindistance = sys.maxsize
def __lt__(self, other):
return self.mindistance < other.mindistance
class Edge:
def __init__(self, weight, startvertex, endvertex):
self.weight = weight
self.startvertex = startvertex
self.endvertex = endvertex
def calculateshortestpath(vertexlist, startvertex):
q = []
startvertex.mindistance = 0
heapq.heappush(q, startvertex)
while q:
actualnode = heapq.heappop(q)
for edge in actualnode.adjacenciesList:
tempdist = edge.startvertex.mindistance + edge.weight
if tempdist < edge.endvertex.mindistance:
edge.endvertex.mindistance = tempdist
edge.endvertex.predecessor = edge.startvertex
heapq.heappush(q,edge.endvertex)
def getshortestpath(targetvertex):
print("The value of it's minimum distance is: ",targetvertex.mindistance)
node = targetvertex
while node:
print(node.name)
node = node.predecessor
node1 = Node("A");
node2 = Node("B");
node3 = Node("C");
node4 = Node("D");
node5 = Node("E");
node6 = Node("F");
node7 = Node("G");
node8 = Node("H");
edge1 = Edge(5,node1,node2);
edge2 = Edge(8,node1,node8);
edge3 = Edge(9,node1,node5);
edge4 = Edge(15,node2,node4);
edge5 = Edge(12,node2,node3);
edge6 = Edge(4,node2,node8);
edge7 = Edge(7,node8,node3);
edge8 = Edge(6,node8,node6);
edge9 = Edge(5,node5,node8);
edge10 = Edge(4,node5,node6);
edge11 = Edge(20,node5,node7);
edge12 = Edge(1,node6,node3);
edge13 = Edge(13,node6,node7);
edge14 = Edge(3,node3,node4);
edge15 = Edge(11,node3,node7);
edge16 = Edge(9,node4,node7);
node1.adjacenciesList.append(edge1);
node1.adjacenciesList.append(edge2);
node1.adjacenciesList.append(edge3);
node2.adjacenciesList.append(edge4);
node2.adjacenciesList.append(edge5);
node2.adjacenciesList.append(edge6);
node8.adjacenciesList.append(edge7);
node8.adjacenciesList.append(edge8);
node5.adjacenciesList.append(edge9);
node5.adjacenciesList.append(edge10);
node5.adjacenciesList.append(edge11);
node6.adjacenciesList.append(edge12);
node6.adjacenciesList.append(edge13);
node3.adjacenciesList.append(edge14);
node3.adjacenciesList.append(edge15);
node4.adjacenciesList.append(edge16);
vertexlist = (node1,node2,node3,node4,node5,node6,node7,node8)
calculateshortestpath(vertexlist,node1)
getshortestpath(node7)
回答by Enzo Lizama
This implementation use only array and heap ds.
此实现仅使用数组和堆 ds。
import heapq as hq
import math
def dijkstra(G, s):
n = len(G)
visited = [False]*n
weights = [math.inf]*n
path = [None]*n
queue = []
weights[s] = 0
hq.heappush(queue, (0, s))
while len(queue) > 0:
g, u = hq.heappop(queue)
visited[u] = True
for v, w in G[u]:
if not visited[v]:
f = g + w
if f < weights[v]:
weights[v] = f
path[v] = u
hq.heappush(queue, (f, v))
return path, weights
G = [[(1, 6), (3, 7)],
[(2, 5), (3, 8), (4, -4)],
[(1, -2), (4, 7)],
[(2, -3), (4, 9)],
[(0, 2)]]
print(dijkstra(G, 0))
I hope this could help someone, it's a little bit late.
我希望这可以帮助某人，这有点晚了。
回答by Carlos Tomas Nolf Kutscher
I broke down the wikipedia description into the following pseudo-code on my blog rebrained.com:
我在我的博客 rebrained.com 上将维基百科描述分解为以下伪代码：
Initial state:
初始状态：
- give nodes two properties - node.visited and node.distance
- set node.distance = infinity for all nodes except set start node to zero
- set node.visited = false for all nodes
- set current node = start node.
- 给节点两个属性 - node.visited 和 node.distance
- 为所有节点设置 node.distance = 无穷大，除了将起始节点设置为零
- 为所有节点设置 node.visited = false
- 设置当前节点 = 起始节点。
Current node loop:
当前节点循环：
- if current node = end node, finish and return current.distance & path
- for all unvisited neighbors, calc their tentative distance (current.distance + edge to neighbor).
- if tentative distance < neighbor's set distance, overwrite it.
- set current.isvisited = true.
- set current = remaining unvisited node with smallest node.distance
- 如果当前节点 = 结束节点，完成并返回 current.distance & path
- 对于所有未访问的邻居，计算他们的暂定距离（current.distance + edge to neighbor）。
- 如果暂定距离 < 邻居设置的距离，则覆盖它。
- 设置 current.isvisited = true。
- 设置当前 = 具有最小 node.distance 的剩余未访问节点
import sys
def shortestpath(graph,start,end,visited=[],distances={},predecessors={}):
"""Find the shortest path btw start & end nodes in a graph"""
# detect if first time through, set current distance to zero
if not visited: distances[start]=0
# if we've found our end node, find the path to it, and return
if start==end:
path=[]
while end != None:
path.append(end)
end=predecessors.get(end,None)
return distances[start], path[::-1]
# process neighbors as per algorithm, keep track of predecessors
for neighbor in graph[start]:
if neighbor not in visited:
neighbordist = distances.get(neighbor,sys.maxint)
tentativedist = distances[start] + graph[start][neighbor]
if tentativedist < neighbordist:
distances[neighbor] = tentativedist
predecessors[neighbor]=start
# neighbors processed, now mark the current node as visited
visited.append(start)
# finds the closest unvisited node to the start
unvisiteds = dict((k, distances.get(k,sys.maxint)) for k in graph if k not in visited)
closestnode = min(unvisiteds, key=unvisiteds.get)
# now take the closest node and recurse, making it current
return shortestpath(graph,closestnode,end,visited,distances,predecessors)
if __name__ == "__main__":
graph = {'a': {'w': 14, 'x': 7, 'y': 9},
'b': {'w': 9, 'z': 6},
'w': {'a': 14, 'b': 9, 'y': 2},
'x': {'a': 7, 'y': 10, 'z': 15},
'y': {'a': 9, 'w': 2, 'x': 10, 'z': 11},
'z': {'b': 6, 'x': 15, 'y': 11}}
print shortestpath(graph,'a','a')
print shortestpath(graph,'a','b')
"""
Expected Result:
(0, ['a'])
(20, ['a', 'y', 'w', 'b'])
"""
回答by Yossarian42
Here is my implementation of Dijkstra algorithm using min-priority-queue. Hope it will you.
这是我使用最小优先级队列实现的 Dijkstra 算法。希望你会。
from collections import defaultdict
from math import floor
class MinPQ:
"""
each heap element is in form (key value, object handle), while heap
operations works based on comparing key value and object handle points to
the corresponding application object.
"""
def __init__(self, array=[]):
self._minheap = list(array)
self._length = len(array)
self._heapsize = 0
self._build_min_heap()
def _left(self, idx):
return 2*idx+1
def _right(self, idx):
return 2*idx+2
def _parent(self, idx):
return floor((idx-1)/2)
def _min_heapify(self, idx):
left = self._left(idx)
right = self._right(idx)
min_idx = idx
if left <= self._heapsize-1 and self._minheap[left] < self._minheap[min_idx]:
min_idx = left
if right <= self._heapsize-1 and self._minheap[right] < self._minheap[min_idx]:
min_idx = right
if min_idx != idx:
self._minheap[idx], self._minheap[min_idx] = self._minheap[min_idx], self._minheap[idx]
self._min_heapify(min_idx)
def _build_min_heap(self):
self._heapsize = self._length
mid_id = int(self._heapsize-1)-1
for i in range(mid_id, -1, -1):
self._min_heapify(i)
def decrease_key(self, idx, new_key):
while idx > 0 and new_key < self._minheap[self._parent(idx)]:
self._minheap[idx] = self._minheap[self._parent(idx)]
idx = self._parent(idx)
self._minheap[idx] = new_key
def extract_min(self):
minimum = self._minheap[0]
self._minheap[0] = self._minheap[self._heapsize-1]
self._heapsize = self._heapsize - 1
self._min_heapify(0)
return minimum
def insert(self, item):
self._minheap.append(item)
self._heapsize = self._heapsize + 1
self.decrease_key(self._heapsize-1, item)
@property
def minimum(self):
return self._minheap[0]
def is_empty(self):
return self._heapsize == 0
def __str__(self):
return str(self._minheap)
__repr__ = __str__
def __len__(self):
return self._heapsize
class DiGraph:
def __init__(self, edges=None):
self.adj_list = defaultdict(list)
self.add_weighted_edges(edges)
@property
def nodes(self):
nodes = set()
nodes.update(self.adj_list.keys())
for node in self.adj_list.keys():
for neighbor, weight in self.adj_list[node]:
nodes.add(neighbor)
return list(nodes)
def add_weighted_edges(self, edges):
if edges is None:
return None
for edge in edges:
self.add_weighted_edge(edge)
def add_weighted_edge(self, edge):
node1, node2, weight = edge
self.adj_list[node1].append((node2, weight))
def weight(self, tail, head):
for node, weight in self.adj_list[tail]:
if node == head:
return weight
return None
def relax(min_heapq, dist, graph, u, v):
if dist[v] > dist[u] + graph.weight(u, v):
dist[v] = dist[u] + graph.weight(u, v)
min_heapq.insert((dist[v], v))
def dijkstra(graph, start):
# initialize
dist = dict.fromkeys(graph.nodes, float('inf'))
dist[start] = 0
min_heapq = MinPQ()
min_heapq.insert((0, start))
while not min_heapq.is_empty():
distance, u = min_heapq.extract_min()
# we may add a node multiple time in priority queue, but we process it
# only once
if distance > dist[u]:
continue
for neighbor, weight in graph.adj_list[u]:
relax(min_heapq, dist, graph, u, neighbor)
return dist
if __name__ == "__main__":
edges = [('s', 't', 10), ('t', 'x', 1), ('s', 'y', 5), ('y', 't', 3), ('t', 'y', 2),
('y', 'x', 9), ('y', 'z', 2), ('z', 's', 7), ('x', 'z', 4), ('z', 'x', 6)]
digraph = DiGraph(edges)
res = dijkstra(digraph, 's')
print(res)
回答by Yossarian42
I implement Dijkstra using priority-queue. Apart from that, I also implement min-heap myself. Hope this will help you.
我使用优先级队列实现 Dijkstra。除此之外，我还自己实现了最小堆。希望这会帮助你。
from collections import defaultdict
class MinPQ:
"""
each heap element is in form (key value, object handle), while heap
operations works based on comparing key value and object handle points to
the corresponding application object.
"""
def __init__(self, array=[]):
self._minheap = list(array)
self._length = len(array)
self._heapsize = 0
self._build_min_heap()
def _left(self, idx):
return 2*idx+1
def _right(self, idx):
return 2*idx+2
def _parent(self, idx):
return int((idx-1)/2)
def _min_heapify(self, idx):
left = self._left(idx)
right = self._right(idx)
min_idx = idx
if left <= self._heapsize-1 and self._minheap[left] < self._minheap[min_idx]:
min_idx = left
if right <= self._heapsize-1 and self._minheap[right] < self._minheap[min_idx]:
min_idx = right
if min_idx != idx:
self._minheap[idx], self._minheap[min_idx] = self._minheap[min_idx], self._minheap[idx]
self._min_heapify(min_idx)
def _build_min_heap(self):
self._heapsize = self._length
mid_id = int((self._heapsize)/2)-1
for i in range(mid_id, -1, -1):
self._min_heapify(i)
def decrease_key(self, idx, new_key):
while idx > 0 and new_key < self._minheap[self._parent(idx)]:
self._minheap[idx] = self._minheap[self._parent(idx)]
idx = self._parent(idx)
self._minheap[idx] = new_key
def extract_min(self):
if self._heapsize < 1:
raise IndexError
minimum = self._minheap[0]
self._minheap[0] = self._minheap[self._heapsize-1]
self._heapsize = self._heapsize - 1
self._min_heapify(0)
return minimum
def insert(self, item):
self._minheap.append(item)
self._heapsize = self._heapsize + 1
self.decrease_key(self._heapsize-1, item)
@property
def minimum(self):
return self._minheap[0]
def is_empty(self):
return self._heapsize == 0
def __str__(self):
return str(self._minheap)
__repr__ = __str__
def __len__(self):
return self._heapsize
class DiGraph:
def __init__(self, edges=None):
self.adj_list = defaultdict(list)
self.add_weighted_edges(edges)
@property
def nodes(self):
nodes = set()
nodes.update(self.adj_list.keys())
for node in self.adj_list.keys():
for neighbor, weight in self.adj_list[node]:
nodes.add(neighbor)
return list(nodes)
def add_weighted_edges(self, edges):
if edges is None:
return None
for edge in edges:
self.add_weighted_edge(edge)
def add_weighted_edge(self, edge):
node1, node2, weight = edge
self.adj_list[node1].append((node2, weight))
def weight(self, tail, head):
for node, weight in self.adj_list[tail]:
if node == head:
return weight
return None
def relax(min_heapq, dist, graph, u, v):
if dist[v] > dist[u] + graph.weight(u, v):
dist[v] = dist[u] + graph.weight(u, v)
min_heapq.insert((dist[v], v))
def dijkstra(graph, start):
# initialize
dist = dict.fromkeys(graph.nodes, float('inf'))
dist[start] = 0
min_heapq = MinPQ()
min_heapq.insert((0, start))
while not min_heapq.is_empty():
distance, u = min_heapq.extract_min()
# we may add a node multiple time in priority queue, but we process it
# only once
if distance > dist[u]:
continue
for neighbor, weight in graph.adj_list[u]:
relax(min_heapq, dist, graph, u, neighbor)
return dist
回答by Can Tuksavul
Implementation based on CLRS 2nd Ed. Chapter 24.3
基于 CLRS 2nd Ed 的实现。第 24.3 章
dis deltas, pis predecessors
d是增量，p是前辈
import heapq
def dijkstra(g, s, t):
q = []
d = {k: sys.maxint for k in g.keys()}
p = {}
d[s] = 0
heapq.heappush(q, (0, s))
while q:
last_w, curr_v = heapq.heappop(q)
for n, n_w in g[curr_v]:
cand_w = last_w + n_w # equivalent to d[curr_v] + n_w
# print d # uncomment to see how deltas are updated
if cand_w < d[n]:
d[n] = cand_w
p[n] = curr_v
heapq.heappush(q, (cand_w, n))
print "predecessors: ", p
print "delta: ", d
return d[t]
def test():
og = {}
og["s"] = [("t", 10), ("y", 5)]
og["t"] = [("y", 2), ("x", 1)]
og["y"] = [("t", 3), ("x", 9), ("z", 2)]
og["z"] = [("x", 6), ("s", 7)]
og["x"] = [("z", 4)]
assert dijkstra(og, "s", "x") == 9
if __name__ == "__main__":
test()
Implementation assumes all nodes are represented as keys. If say node(e.g "x" in the example above) was not defined as a key in the og, deltas dwould be missing that key and check if cand_w < d[n]wouldn't work correctly.
实现假设所有节点都表示为键。如果说节点（例如上面示例中的“x”）未定义为og 中的键，则deltas d将缺少该键并检查cand_w < d[n]是否无法正常工作。
