执行删除节点时 Dijkstra 算法出错
Error in Dijkstra Algorithm while executing in removing the nodes
我正在尝试按如下方式实现 Dijkstra 算法：
from collections import defaultdict
class Graph:
def __init__(self):
self.nodes = set()
self.edges = defaultdict(list)
self.distances = {}
def add_node(self, value):
self.nodes.add(value)
def add_edge(self, from_node, to_node, distance):
self.edges[from_node].append(to_node)
self.edges[to_node].append(from_node)
self.distances[(from_node, to_node)] = distance
def dijsktra(graph, initial):
visited = {initial: 0}
path = {}
nodes = set(graph.nodes)
while nodes:
min_node = None
for node in nodes:
if node in visited:
if min_node is None:
min_node = node
elif visited[node] < visited[min_node]:
min_node = node
if min_node is None:
break
nodes.remove(min_node)
current_weight = visited[min_node]
for edge in graph.edges[min_node]:
weight = current_weight + graph.distances[(min_node, edge)]
if edge not in visited or weight < visited[edge]:
visited[edge] = weight
path[edge] = min_node
return visited, path
我有 36 个具有方向权重的连接节点。我已经制作了图表。具有权重的节点和连接边如下：
print(g.nodes)
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35}
print(g.distances)
{(1, 7): 2, (1, 2): 2, (2, 1): 1, (2, 3): 4, (3, 2): 2, (3, 9): 2, (5, 11): 1, (5, 6): 1,
(6, 5): 3, (6, 12): 2, (7, 1): 1, (7, 13): 3, (9, 3): 4, (9, 15): 1, (11, 5): 3, (11, 17):
3, (11, 12): 2, (12, 6): 1, (12, 11): 1, (12, 18): 2, (13, 7): 2, (13, 14): 2, (14, 13): 3,
(14, 20): 1, (14, 15): 1, (15, 9): 2, (15, 14): 2, (15, 21): 2, (15, 16): 4, (16, 15): 1,
(16, 22): 1, (16, 17): 3, (17, 11): 1, (17, 16): 4, (17, 18): 2, (18, 12): 2, (18, 17): 3,
(18, 24): 1, (20, 14): 2, (20, 26): 1, (20, 21): 2, (21, 15): 1, (21, 20): 1, (21, 27): 1,
(21, 22): 1, (22, 16): 4, (22, 21): 2, (24, 18): 2, (24, 30): 1, (25, 31): 1, (25, 26): 1,
(26, 20): 1, (26, 25): 2, (26, 27): 1, (27, 21): 2, (27, 26): 1, (27, 33): 4, (30, 24): 1,
(30, 36): 1, (31, 25): 2, (33, 27): 1, (33, 34): 2, (34, 33): 4, (34, 35): 2, (35, 34): 2,
(35, 36): 1, (36, 30): 1, (36, 35): 2}
但是我在执行时遇到错误。似乎是由于删除了 None。我尝试将 None 更改为 inf。仍然出现相同的错误。我现在该怎么办？
这是函数执行和错误：
visited,path = dijsktra(g,0)
---------------------------------------------------------------------------
KeyError Traceback (most recent call last)
<ipython-input-44-c4a3ba9a32e3> in <module>
----> 1 parent,path=dijsktra(g,0)
<ipython-input-25-cd9030508fd7> in dijsktra(graph, initial)
34
35
---> 36 nodes.remove(min_node)
37 current_weight = visited[min_node]
38
KeyError: None
如何消除错误？请任何人解决这个问题。会有帮助。
谢谢！
编辑：
这是我用来生成 g.nodes 和 g.distances
的代码的 link
我认为您的 dijskstra 函数没有正确实现算法。您通常会初始化一个 dist（距离）字典，其中的键是图的节点值，其值被初始化为无穷大（或合适的大值），但初始节点除外初始化为 0。此字典表示 initial 每个节点到初始节点的距离。然后每次循环迭代寻找一个 unvisited 节点（所有节点最初都是）寻找与初始节点距离最小的节点）。第一次通过循环时，这将是初始节点本身。然后将该节点从未访问节点中删除，并更新从该节点到与该节点相邻的所有节点的距离。最终，所有节点都从未访问节点列表中删除，我们就完成了。我修改了什么函数returns。由于不再有访问字典的概念，它 returns dist 字典给出了到每个节点的距离：
from collections import defaultdict
class Graph:
def __init__(self):
self.nodes = set()
self.edges = defaultdict(list)
self.distances = {}
def add_node(self, value):
self.nodes.add(value)
def add_edge(self, from_node, to_node, distance):
self.edges[from_node].append(to_node)
self.edges[to_node].append(from_node)
self.distances[(from_node, to_node)] = distance
self.distances[(to_node, from_node)] = distance
def dijsktra(graph, initial): # should be dijkstra
nodes = set(graph.nodes) # unvisted nodes
path = {}
dist = {node: 999999999999999 for node in nodes} # assume this is larger than any actual distance
dist[initial] = 0
while nodes: # we still have unvisted nodes
min_node = None
for node in nodes:
if min_node is None:
min_node = node
elif dist[node] < dist[min_node]:
min_node = node
nodes.remove(min_node)
current_weight = dist[min_node]
for edge in graph.edges[min_node]:
weight = current_weight + graph.distances[(min_node, edge)]
if weight < dist[edge]:
dist[edge] = weight
path[edge] = min_node
return dist, path
"code to generate nodes:"
g=Graph()
g.add_node(1)
g.add_node(2)
g.add_node(3)
g.add_node(4)
g.add_edge(1, 2, 1)
g.add_edge(1, 3, 2)
g.add_edge(2, 4, 5)
g.add_edge(3, 4, 1)
print(dijsktra(g, 1))
打印：
({1: 0, 2: 1, 3: 2, 4: 3}, {2: 1, 3: 1, 4: 3})
更新
我想我会添加一个更高效的修改版本。我们不是让所有节点最初都在我们的“未访问节点列表”中进行处理，而是维护一个节点列表，该列表与初始节点的最终距离已计算但其相邻节点尚未处理。从这个列表中，我们总是希望 select 与初始节点的距离具有最小值的节点。为此，每个节点现在都是一个元组，由它与初始节点的距离及其节点值组成。这些节点维护在 heap queue 中，自动生成具有最小值的节点：
from collections import defaultdict
from heapq import heappop, heappush
class Graph:
def __init__(self):
self.nodes = set()
self.edges = defaultdict(list)
self.distances = {}
def add_node(self, value):
self.nodes.add(value)
def add_edge(self, from_node, to_node, distance):
self.edges[from_node].append(to_node)
self.edges[to_node].append(from_node)
self.distances[(from_node, to_node)] = distance
self.distances[(to_node, from_node)] = distance
def dijkstra(graph, initial): # should be dijkstra
visited = set()
path = {}
priority_queue = []
INFINITY = float('inf')
distances = {node: INFINITY for node in graph.nodes}
dist[initial] = 0
heappush(priority_queue, (0, initial)) # (cost, initial)
while priority_queue:
_, min_node = heappop(priority_queue)
visited.add(min_node)
current_weight = dist[min_node]
for edge in graph.edges[min_node]: # this is really a node and not an edge
if edge in visited:
continue
weight = current_weight + graph.distances[(min_node, edge)]
if weight < dist[edge]:
dist[edge] = weight
path[edge] = min_node
heappush(priority_queue, (weight, edge))
return dist, path
g = Graph()
g.add_node(1)
g.add_node(2)
g.add_node(3)
g.add_node(4)
g.add_edge(1, 2, 1)
g.add_edge(1, 3, 2)
g.add_edge(2, 4, 5)
g.add_edge(3, 4, 1)
print(dijkstra(g, 1))
我正在尝试按如下方式实现 Dijkstra 算法：
from collections import defaultdict
class Graph:
def __init__(self):
self.nodes = set()
self.edges = defaultdict(list)
self.distances = {}
def add_node(self, value):
self.nodes.add(value)
def add_edge(self, from_node, to_node, distance):
self.edges[from_node].append(to_node)
self.edges[to_node].append(from_node)
self.distances[(from_node, to_node)] = distance
def dijsktra(graph, initial):
visited = {initial: 0}
path = {}
nodes = set(graph.nodes)
while nodes:
min_node = None
for node in nodes:
if node in visited:
if min_node is None:
min_node = node
elif visited[node] < visited[min_node]:
min_node = node
if min_node is None:
break
nodes.remove(min_node)
current_weight = visited[min_node]
for edge in graph.edges[min_node]:
weight = current_weight + graph.distances[(min_node, edge)]
if edge not in visited or weight < visited[edge]:
visited[edge] = weight
path[edge] = min_node
return visited, path
我有 36 个具有方向权重的连接节点。我已经制作了图表。具有权重的节点和连接边如下：
print(g.nodes)
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35}
print(g.distances)
{(1, 7): 2, (1, 2): 2, (2, 1): 1, (2, 3): 4, (3, 2): 2, (3, 9): 2, (5, 11): 1, (5, 6): 1,
(6, 5): 3, (6, 12): 2, (7, 1): 1, (7, 13): 3, (9, 3): 4, (9, 15): 1, (11, 5): 3, (11, 17):
3, (11, 12): 2, (12, 6): 1, (12, 11): 1, (12, 18): 2, (13, 7): 2, (13, 14): 2, (14, 13): 3,
(14, 20): 1, (14, 15): 1, (15, 9): 2, (15, 14): 2, (15, 21): 2, (15, 16): 4, (16, 15): 1,
(16, 22): 1, (16, 17): 3, (17, 11): 1, (17, 16): 4, (17, 18): 2, (18, 12): 2, (18, 17): 3,
(18, 24): 1, (20, 14): 2, (20, 26): 1, (20, 21): 2, (21, 15): 1, (21, 20): 1, (21, 27): 1,
(21, 22): 1, (22, 16): 4, (22, 21): 2, (24, 18): 2, (24, 30): 1, (25, 31): 1, (25, 26): 1,
(26, 20): 1, (26, 25): 2, (26, 27): 1, (27, 21): 2, (27, 26): 1, (27, 33): 4, (30, 24): 1,
(30, 36): 1, (31, 25): 2, (33, 27): 1, (33, 34): 2, (34, 33): 4, (34, 35): 2, (35, 34): 2,
(35, 36): 1, (36, 30): 1, (36, 35): 2}
但是我在执行时遇到错误。似乎是由于删除了 None。我尝试将 None 更改为 inf。仍然出现相同的错误。我现在该怎么办？
这是函数执行和错误：
visited,path = dijsktra(g,0)
---------------------------------------------------------------------------
KeyError Traceback (most recent call last)
<ipython-input-44-c4a3ba9a32e3> in <module>
----> 1 parent,path=dijsktra(g,0)
<ipython-input-25-cd9030508fd7> in dijsktra(graph, initial)
34
35
---> 36 nodes.remove(min_node)
37 current_weight = visited[min_node]
38
KeyError: None
如何消除错误？请任何人解决这个问题。会有帮助。
谢谢！
编辑：
这是我用来生成 g.nodes 和 g.distances
我认为您的 dijskstra 函数没有正确实现算法。您通常会初始化一个 dist（距离）字典，其中的键是图的节点值，其值被初始化为无穷大（或合适的大值），但初始节点除外初始化为 0。此字典表示 initial 每个节点到初始节点的距离。然后每次循环迭代寻找一个 unvisited 节点（所有节点最初都是）寻找与初始节点距离最小的节点）。第一次通过循环时，这将是初始节点本身。然后将该节点从未访问节点中删除，并更新从该节点到与该节点相邻的所有节点的距离。最终，所有节点都从未访问节点列表中删除，我们就完成了。我修改了什么函数returns。由于不再有访问字典的概念，它 returns dist 字典给出了到每个节点的距离：
from collections import defaultdict
class Graph:
def __init__(self):
self.nodes = set()
self.edges = defaultdict(list)
self.distances = {}
def add_node(self, value):
self.nodes.add(value)
def add_edge(self, from_node, to_node, distance):
self.edges[from_node].append(to_node)
self.edges[to_node].append(from_node)
self.distances[(from_node, to_node)] = distance
self.distances[(to_node, from_node)] = distance
def dijsktra(graph, initial): # should be dijkstra
nodes = set(graph.nodes) # unvisted nodes
path = {}
dist = {node: 999999999999999 for node in nodes} # assume this is larger than any actual distance
dist[initial] = 0
while nodes: # we still have unvisted nodes
min_node = None
for node in nodes:
if min_node is None:
min_node = node
elif dist[node] < dist[min_node]:
min_node = node
nodes.remove(min_node)
current_weight = dist[min_node]
for edge in graph.edges[min_node]:
weight = current_weight + graph.distances[(min_node, edge)]
if weight < dist[edge]:
dist[edge] = weight
path[edge] = min_node
return dist, path
"code to generate nodes:"
g=Graph()
g.add_node(1)
g.add_node(2)
g.add_node(3)
g.add_node(4)
g.add_edge(1, 2, 1)
g.add_edge(1, 3, 2)
g.add_edge(2, 4, 5)
g.add_edge(3, 4, 1)
print(dijsktra(g, 1))
打印：
({1: 0, 2: 1, 3: 2, 4: 3}, {2: 1, 3: 1, 4: 3})
更新
我想我会添加一个更高效的修改版本。我们不是让所有节点最初都在我们的“未访问节点列表”中进行处理，而是维护一个节点列表，该列表与初始节点的最终距离已计算但其相邻节点尚未处理。从这个列表中，我们总是希望 select 与初始节点的距离具有最小值的节点。为此，每个节点现在都是一个元组，由它与初始节点的距离及其节点值组成。这些节点维护在 heap queue 中，自动生成具有最小值的节点：
from collections import defaultdict
from heapq import heappop, heappush
class Graph:
def __init__(self):
self.nodes = set()
self.edges = defaultdict(list)
self.distances = {}
def add_node(self, value):
self.nodes.add(value)
def add_edge(self, from_node, to_node, distance):
self.edges[from_node].append(to_node)
self.edges[to_node].append(from_node)
self.distances[(from_node, to_node)] = distance
self.distances[(to_node, from_node)] = distance
def dijkstra(graph, initial): # should be dijkstra
visited = set()
path = {}
priority_queue = []
INFINITY = float('inf')
distances = {node: INFINITY for node in graph.nodes}
dist[initial] = 0
heappush(priority_queue, (0, initial)) # (cost, initial)
while priority_queue:
_, min_node = heappop(priority_queue)
visited.add(min_node)
current_weight = dist[min_node]
for edge in graph.edges[min_node]: # this is really a node and not an edge
if edge in visited:
continue
weight = current_weight + graph.distances[(min_node, edge)]
if weight < dist[edge]:
dist[edge] = weight
path[edge] = min_node
heappush(priority_queue, (weight, edge))
return dist, path
g = Graph()
g.add_node(1)
g.add_node(2)
g.add_node(3)
g.add_node(4)
g.add_edge(1, 2, 1)
g.add_edge(1, 3, 2)
g.add_edge(2, 4, 5)
g.add_edge(3, 4, 1)
print(dijkstra(g, 1))