将 Dijkstra 与 heapq 一起应用：'generator' object 不可订阅
Applying Dijkstra with heapq: 'generator' object is not subscriptable
如标题所示，我正在尝试将 dijkstra 算法与 Heapq 一起应用（在 python 中的 dijksta 上 bogotobogo.com 稍作修改 - 长 link；无法输入), 我得到 TypeError: 'generator' object is not subscriptable with the result of heapq.heappop over a heapified list (在下面的代码中我使用了 print('the problem is in the line above ... ')找到错误），我试图避免首先生成生成器的情况（如在列表理解中使用元组 - ）但没有运气。
感谢您提供任何帮助，因为这里的移动幅度很小。
import sys
import heapq
# making the vertices
class Vertex:
"""
a class for making the vertex data structure that will be used to compose the graph and added to the shortest path.
"""
def __init__(self,node_id):
self.id = node_id
self.distance = sys.maxsize
self.visited = False
# adding the adjacent
self.neighbors = {}
#empty object holding previous vertices
self.previous = {}
def add_neighbors(self,neighbor,cost=0):
# adding neighbors to the node when it is traversed
self.neighbors[neighbor] = cost
def get_neighbors(self):
return self.neighbors
def get_cost(self,neighbor):
# get the weigh previously set on add_neighbors.
return self.neighbors[neighbor]
def set_visited(self):
self.visited=True
def set_distance(self,distance):
self.distance = distance
def get_distance(self):
return self.distance
def add_previous(self,previous):
self.previous.append(previous)
def get_previous(self):
return self.previous
def get_id(self):
return self.id
# def __getitem__(self, item):
# return self.neighbors[item]
def __lt__(self,other_vertex):
# this is used by python class for making comparsions -> required by the heapq
return self.distance < other_vertex.distance
class Graph:
def __init__(self):
self.vertices_dict = {}
self.num_vertices = 0
def __iter__(self): # this will cause this class to be iterable
return iter(self.vertices_dict.values())
def get_dict_values(self):
return self.vertices_dict.value()
def add_vertex(self,node):
new_vertex = Vertex(node)
self.vertices_dict[node] = new_vertex
self.num_vertices+=1
return new_vertex
def get_vertex(self,node):
if node in self.vertices_dict:
return self.vertices_dict[node]
else:
return None
def construct_edge(self,From,to,cost=0):
"""
take from and to (Vertices) to make the edge, check if these Vertices already exists on the vertices_dict
if not add them, and then call Vertex add_neighbors() method.
"""
if From not in self.vertices_dict:
self.add_vertex(From)
elif to not in self.vertices_dict:
self.add_vertex(to)
self.vertices_dict[From].add_neighbors(self.vertices_dict[to],cost)
self.vertices_dict[to].add_neighbors(self.vertices_dict[From],cost)
def construct_shortest_path(self,v,path):
"""
recursively construct the shortest path from the vertex previous.
"""
if v.previous:
path.append(v.previous.get_id())
# recursion
construct_shortest_path(v.previous,path)
def dijkstra(graph,start,end):
"""
1. adjust the distance of the start and add it to a list of unvisited_vertices "also known as openSet"
2. get vertices and their indexes from the graph.
3. loop until the len of unvisited_vertices equals 0.
4. pop the first item of the unvisited_vertices and adjust it's visited value, name the item current.
5. loop the neighbors of current, and check if it is already visited
5.1 if not make a new distance equals to current vertex distance+ the cost from current ot next
if this distance is less the distance of the neighbor, assign it to the neighbor instead and
assign previous in the neighbors properties to current so you can keep track of previous vertices.
if it is not less the distance of the nighbor don't do anything.
6. the shortest path is stored in the previous of the nodes, another function has to handle extracting the
path (construct_shortest_path).
note that the dijkstra function steps is slightly more complicated as heaps are used to organize data.
"""
start.set_distance(0)
unvisited_nodes = [[vertex.get_distance(),vertex] for vertex in graph]
#unvisited_nodes.append(start) # the start is assumed to be outer to the graph (not added to it already)
# heapify the list so the the least distance is at the begining
print('Before being heapified:',unvisited_nodes)
heapq.heapify(unvisited_nodes)
print(unvisited_nodes)
while(len(unvisited_nodes)):
heap_tuple = heapq.heappop(unvisited_nodes) # using heappop instead of pop.
print("Heap tuple:",heap_tuple)
print("Heap vertex:",heap_tuple[1])
print("the problem is in the line above ... ")
current = heap_tuple[1]
print('Current:',current)
current.set_visited()
if current==end:
break
for next in current.neighbors:
if next.visited:
continue
tentative_distance = current.get_distance()+current.get_cost(next)
if tentative_distance < next.get_distance():
next.set_distance = tentative_distance
next.previous = current
else:
continue
# heap rebuild (i don't believe this is a good practice, there should be another way to refresh the heapq)
# empty the heap
while(len(unvisited_nodes)):
heapq.heappop(unvisited_nodes)
# again add vertices unvisited to it
unvisited_nodes.append([v.get_distance(),v] for v in graph)
heapq.heapify(unvisited_nodes)
print('Reached the end')
if __name__ == '__main__':
g = Graph()
g.add_vertex('a')
g.add_vertex('b')
g.add_vertex('c')
g.add_vertex('d')
g.add_vertex('e')
g.add_vertex('f')
g.construct_edge('a', 'b', 7)
g.construct_edge('a', 'c', 9)
g.construct_edge('a', 'f', 14)
g.construct_edge('b', 'c', 10)
g.construct_edge('b', 'd', 15)
g.construct_edge('c', 'd', 11)
g.construct_edge('c', 'f', 2)
g.construct_edge('d', 'e', 6)
g.construct_edge('e', 'f', 9)
print ('Graph data:',g)
for v in g.vertices_dict.values():
for w in v.get_neighbors():
vid = v.get_id()
wid = w.get_id()
txt = '{}, {}, {}'.format(vid,wid,v.get_cost(w))
print(txt)
dijkstra(g, g.get_vertex('a'), g.get_vertex('e'))
target = g.get_vertex('e')
path = [target.get_id()]
shortest(target, path)
tx = 'The shortest path:{}'.format(path[::-1])
print(tx)
在函数 dijkstra 的倒数第三行中，您仍在使用生成器。
unvisited_nodes.append((v.get_distance(),v) for v in graph)
将其转换为列表以使用订阅访问。
for v in graph:
unvisited_nodes.append([v.get_distance(),v])
我正在添加另一个答案作为对你发布的关于无限循环的问题的回应。
我在这里查看了 3 个视频：
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/rxrPa/dijkstras-shortest-path-algorithm
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/Jfvmn/dijkstras-algorithm-examples
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/Pbpp9/dijkstras-algorithm-implementation-and-running-time
然后使用您的顶点和图形代码，但修改了 djikstra 函数以执行以下操作：
- 创建开始邻居列表
- 选择最小邻居节点
- 更改所选节点邻居的距离值
- 重复直到列表为空，因为所有其他都没有连接到开始所以我们不关心
下面粘贴了整个文件
import sys
import heapq
# making the vertices
class Vertex:
"""
a class for making the vertex data structure that will be used to compose the graph and added to the shortest path. # noqa:E501
"""
def __init__(self, node_id):
self.id = node_id
self.distance = sys.maxsize
self.visited = False
# adding the adjacent
self.neighbors = {}
# empty object holding previous vertices
self.previous = None
def __str__(self):
return f'Id={self.id}, Dis={self.distance};'
def __repr__(self):
return f'Id={self.id}, Dis={self.distance};'
def add_neighbors(self, neighbor, cost=0):
# adding neighbors to the node when it is traversed
self.neighbors[neighbor] = cost
def get_neighbors(self):
return self.neighbors
def get_cost(self, neighbor):
# get the weigh previously set on add_neighbors.
return self.neighbors[neighbor]
def set_visited(self):
self.visited = True
def set_distance(self, distance):
self.distance = distance
def get_distance(self):
return self.distance
def add_previous(self, previous):
self.previous.append(previous)
def get_previous(self):
return self.previous
def get_id(self):
return self.id
# def __getitem__(self, item):
# return self.neighbors[item]
def __lt__(self, other_vertex):
# this is used by python class for making comparsions -> required by the heapq # noqa:E501
return self.distance < other_vertex.distance
class Graph:
def __init__(self):
self.vertices_dict = {}
self.num_vertices = 0
def __iter__(self): # this will cause this class to be iterable
return iter(self.vertices_dict.values())
def get_dict_values(self):
return self.vertices_dict.value()
def add_vertex(self, node):
new_vertex = Vertex(node)
self.vertices_dict[node] = new_vertex
self.num_vertices += 1
return new_vertex
def get_vertex(self, node):
if node in self.vertices_dict:
return self.vertices_dict[node]
else:
return None
def construct_edge(self, From, to, cost=0):
"""
take from and to (Vertices) to make the edge, check if these Vertices already exists on the vertices_dict # noqa:E501
if not add them, and then call Vertex add_neighbors() method.
"""
if From not in self.vertices_dict:
self.add_vertex(From)
if to not in self.vertices_dict:
self.add_vertex(to)
self.vertices_dict[From].add_neighbors(self.vertices_dict[to], cost)
self.vertices_dict[to].add_neighbors(self.vertices_dict[From], cost)
def construct_shortest_path(self, v, path):
for k, vvv in self.vertices_dict.items():
print(vvv)
"""
recursively construct the shortest path from the vertex previous.
"""
if v.previous:
path.append(v.previous.get_id())
# recursion
self.construct_shortest_path(v.previous, path)
def dijkstra(graph, start, end):
"""
1. adjust the distance of the start and add it to a list of unvisited_vertices "also known as openSet" # noqa:E501
2. get vertices and their indexes from the graph.
3. loop until the len of unvisited_vertices equals 0.
4. pop the first item of the unvisited_vertices and adjust it's visited value, name the item current.
5. loop the neighbors of current, and check if it is already visited
5.1 if not make a new distance equals to current vertex distance+ the cost from current ot next
if this distance is less the distance of the neighbor, assign it to the neighbor instead and
assign previous +current.get_costhortest_path).
note that the dijkstra function steps is slightly more complicated as heaps are used to organize data.
"""
start.set_distance(0)
# 1. create list of start neighbors
# 2. pick least neighbor node
# 3. change distance values of picked node's neighbours
# 4. repeat until list is empty because all else are not connected to start so we dont care # noqa:E501
unvisited_nodes = [vertex for vertex in start.get_neighbors()] # 1 # noqa:E501
# unvisited_nodes.append(start) # the start is assumed to be outer to the graph (not added to it already) # noqa:E501
# heapify the list so the the least distance is at the begining
# print('Before being heapified:', unvisited_nodes)
start.set_visited()
for vertics in unvisited_nodes:
vertics.previous = start
vertics.distance = start.get_cost(vertics)
heapq.heapify(unvisited_nodes)
print(unvisited_nodes)
# import pdb
# pdb.set_trace()
while(len(unvisited_nodes)):
vertics_from_heap = heapq.heappop(unvisited_nodes) # 2 # using heappop instead of pop. # noqa:E501
# print("Heap tuple:", heap_tuple)
# print("Heap vertex:", heap_tuple[1])
# print("the problem is in the line above ... ")
current = vertics_from_heap
print('Current:', current)
current.set_visited()
if current == end:
# current.previous = start
break
for next in current.neighbors:
if next.visited:
continue
tentative_distance = current.get_distance()+current.get_cost(next)
if next not in unvisited_nodes:
heapq.heappush(unvisited_nodes, next)
if tentative_distance < next.get_distance():
next.set_distance = tentative_distance
next.previous = current
# heap rebuild (i don't believe this is a good practice, there should be another way to refresh the heapq) # noqa:E501
# empty the heap
# while(len(unvisited_nodes)):
# heapq.heappop(unvisited_nodes)
# again add vertices unvisited to it
# for v in graph:
# unvisited_nodes.append([v.get_distance(), v])
# heapq.heapify(unvisited_nodes)
# print('Reached the end')
if __name__ == '__main__':
g = Graph()
g.add_vertex('a')
g.add_vertex('b')
g.add_vertex('c')
g.add_vertex('d')
g.add_vertex('e')
g.add_vertex('f')
g.construct_edge('a', 'b', 7)
g.construct_edge('a', 'c', 9)
g.construct_edge('a', 'f', 14)
g.construct_edge('b', 'c', 10)
g.construct_edge('b', 'd', 15)
g.construct_edge('c', 'd', 11)
g.construct_edge('c', 'f', 2)
g.construct_edge('d', 'e', 6)
g.construct_edge('e', 'f', 9)
print('Graph data:', g)
for v in g.vertices_dict.values():
for w in v.get_neighbors():
vid = v.get_id()
wid = w.get_id()
txt = '{}, {}, {}'.format(vid, wid, v.get_cost(w))
print(txt)
dijkstra(g, g.get_vertex('a'), g.get_vertex('e'))
target = g.get_vertex('e')
path = [target.get_id()]
g.construct_shortest_path(target, path)
tx = 'The shortest path:{}'.format(path[::-1])
print(tx)
如标题所示，我正在尝试将 dijkstra 算法与 Heapq 一起应用（在 python 中的 dijksta 上 bogotobogo.com 稍作修改 - 长 link；无法输入), 我得到 TypeError: 'generator' object is not subscriptable with the result of heapq.heappop over a heapified list (在下面的代码中我使用了 print('the problem is in the line above ... ')找到错误），我试图避免首先生成生成器的情况（如在列表理解中使用元组 -
import sys
import heapq
# making the vertices
class Vertex:
"""
a class for making the vertex data structure that will be used to compose the graph and added to the shortest path.
"""
def __init__(self,node_id):
self.id = node_id
self.distance = sys.maxsize
self.visited = False
# adding the adjacent
self.neighbors = {}
#empty object holding previous vertices
self.previous = {}
def add_neighbors(self,neighbor,cost=0):
# adding neighbors to the node when it is traversed
self.neighbors[neighbor] = cost
def get_neighbors(self):
return self.neighbors
def get_cost(self,neighbor):
# get the weigh previously set on add_neighbors.
return self.neighbors[neighbor]
def set_visited(self):
self.visited=True
def set_distance(self,distance):
self.distance = distance
def get_distance(self):
return self.distance
def add_previous(self,previous):
self.previous.append(previous)
def get_previous(self):
return self.previous
def get_id(self):
return self.id
# def __getitem__(self, item):
# return self.neighbors[item]
def __lt__(self,other_vertex):
# this is used by python class for making comparsions -> required by the heapq
return self.distance < other_vertex.distance
class Graph:
def __init__(self):
self.vertices_dict = {}
self.num_vertices = 0
def __iter__(self): # this will cause this class to be iterable
return iter(self.vertices_dict.values())
def get_dict_values(self):
return self.vertices_dict.value()
def add_vertex(self,node):
new_vertex = Vertex(node)
self.vertices_dict[node] = new_vertex
self.num_vertices+=1
return new_vertex
def get_vertex(self,node):
if node in self.vertices_dict:
return self.vertices_dict[node]
else:
return None
def construct_edge(self,From,to,cost=0):
"""
take from and to (Vertices) to make the edge, check if these Vertices already exists on the vertices_dict
if not add them, and then call Vertex add_neighbors() method.
"""
if From not in self.vertices_dict:
self.add_vertex(From)
elif to not in self.vertices_dict:
self.add_vertex(to)
self.vertices_dict[From].add_neighbors(self.vertices_dict[to],cost)
self.vertices_dict[to].add_neighbors(self.vertices_dict[From],cost)
def construct_shortest_path(self,v,path):
"""
recursively construct the shortest path from the vertex previous.
"""
if v.previous:
path.append(v.previous.get_id())
# recursion
construct_shortest_path(v.previous,path)
def dijkstra(graph,start,end):
"""
1. adjust the distance of the start and add it to a list of unvisited_vertices "also known as openSet"
2. get vertices and their indexes from the graph.
3. loop until the len of unvisited_vertices equals 0.
4. pop the first item of the unvisited_vertices and adjust it's visited value, name the item current.
5. loop the neighbors of current, and check if it is already visited
5.1 if not make a new distance equals to current vertex distance+ the cost from current ot next
if this distance is less the distance of the neighbor, assign it to the neighbor instead and
assign previous in the neighbors properties to current so you can keep track of previous vertices.
if it is not less the distance of the nighbor don't do anything.
6. the shortest path is stored in the previous of the nodes, another function has to handle extracting the
path (construct_shortest_path).
note that the dijkstra function steps is slightly more complicated as heaps are used to organize data.
"""
start.set_distance(0)
unvisited_nodes = [[vertex.get_distance(),vertex] for vertex in graph]
#unvisited_nodes.append(start) # the start is assumed to be outer to the graph (not added to it already)
# heapify the list so the the least distance is at the begining
print('Before being heapified:',unvisited_nodes)
heapq.heapify(unvisited_nodes)
print(unvisited_nodes)
while(len(unvisited_nodes)):
heap_tuple = heapq.heappop(unvisited_nodes) # using heappop instead of pop.
print("Heap tuple:",heap_tuple)
print("Heap vertex:",heap_tuple[1])
print("the problem is in the line above ... ")
current = heap_tuple[1]
print('Current:',current)
current.set_visited()
if current==end:
break
for next in current.neighbors:
if next.visited:
continue
tentative_distance = current.get_distance()+current.get_cost(next)
if tentative_distance < next.get_distance():
next.set_distance = tentative_distance
next.previous = current
else:
continue
# heap rebuild (i don't believe this is a good practice, there should be another way to refresh the heapq)
# empty the heap
while(len(unvisited_nodes)):
heapq.heappop(unvisited_nodes)
# again add vertices unvisited to it
unvisited_nodes.append([v.get_distance(),v] for v in graph)
heapq.heapify(unvisited_nodes)
print('Reached the end')
if __name__ == '__main__':
g = Graph()
g.add_vertex('a')
g.add_vertex('b')
g.add_vertex('c')
g.add_vertex('d')
g.add_vertex('e')
g.add_vertex('f')
g.construct_edge('a', 'b', 7)
g.construct_edge('a', 'c', 9)
g.construct_edge('a', 'f', 14)
g.construct_edge('b', 'c', 10)
g.construct_edge('b', 'd', 15)
g.construct_edge('c', 'd', 11)
g.construct_edge('c', 'f', 2)
g.construct_edge('d', 'e', 6)
g.construct_edge('e', 'f', 9)
print ('Graph data:',g)
for v in g.vertices_dict.values():
for w in v.get_neighbors():
vid = v.get_id()
wid = w.get_id()
txt = '{}, {}, {}'.format(vid,wid,v.get_cost(w))
print(txt)
dijkstra(g, g.get_vertex('a'), g.get_vertex('e'))
target = g.get_vertex('e')
path = [target.get_id()]
shortest(target, path)
tx = 'The shortest path:{}'.format(path[::-1])
print(tx)
在函数 dijkstra 的倒数第三行中，您仍在使用生成器。
unvisited_nodes.append((v.get_distance(),v) for v in graph)
将其转换为列表以使用订阅访问。
for v in graph:
unvisited_nodes.append([v.get_distance(),v])
我正在添加另一个答案作为对你发布的关于无限循环的问题的回应。
我在这里查看了 3 个视频：
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/rxrPa/dijkstras-shortest-path-algorithm
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/Jfvmn/dijkstras-algorithm-examples
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/Pbpp9/dijkstras-algorithm-implementation-and-running-time
然后使用您的顶点和图形代码，但修改了 djikstra 函数以执行以下操作：
- 创建开始邻居列表
- 选择最小邻居节点
- 更改所选节点邻居的距离值
- 重复直到列表为空，因为所有其他都没有连接到开始所以我们不关心
下面粘贴了整个文件
import sys
import heapq
# making the vertices
class Vertex:
"""
a class for making the vertex data structure that will be used to compose the graph and added to the shortest path. # noqa:E501
"""
def __init__(self, node_id):
self.id = node_id
self.distance = sys.maxsize
self.visited = False
# adding the adjacent
self.neighbors = {}
# empty object holding previous vertices
self.previous = None
def __str__(self):
return f'Id={self.id}, Dis={self.distance};'
def __repr__(self):
return f'Id={self.id}, Dis={self.distance};'
def add_neighbors(self, neighbor, cost=0):
# adding neighbors to the node when it is traversed
self.neighbors[neighbor] = cost
def get_neighbors(self):
return self.neighbors
def get_cost(self, neighbor):
# get the weigh previously set on add_neighbors.
return self.neighbors[neighbor]
def set_visited(self):
self.visited = True
def set_distance(self, distance):
self.distance = distance
def get_distance(self):
return self.distance
def add_previous(self, previous):
self.previous.append(previous)
def get_previous(self):
return self.previous
def get_id(self):
return self.id
# def __getitem__(self, item):
# return self.neighbors[item]
def __lt__(self, other_vertex):
# this is used by python class for making comparsions -> required by the heapq # noqa:E501
return self.distance < other_vertex.distance
class Graph:
def __init__(self):
self.vertices_dict = {}
self.num_vertices = 0
def __iter__(self): # this will cause this class to be iterable
return iter(self.vertices_dict.values())
def get_dict_values(self):
return self.vertices_dict.value()
def add_vertex(self, node):
new_vertex = Vertex(node)
self.vertices_dict[node] = new_vertex
self.num_vertices += 1
return new_vertex
def get_vertex(self, node):
if node in self.vertices_dict:
return self.vertices_dict[node]
else:
return None
def construct_edge(self, From, to, cost=0):
"""
take from and to (Vertices) to make the edge, check if these Vertices already exists on the vertices_dict # noqa:E501
if not add them, and then call Vertex add_neighbors() method.
"""
if From not in self.vertices_dict:
self.add_vertex(From)
if to not in self.vertices_dict:
self.add_vertex(to)
self.vertices_dict[From].add_neighbors(self.vertices_dict[to], cost)
self.vertices_dict[to].add_neighbors(self.vertices_dict[From], cost)
def construct_shortest_path(self, v, path):
for k, vvv in self.vertices_dict.items():
print(vvv)
"""
recursively construct the shortest path from the vertex previous.
"""
if v.previous:
path.append(v.previous.get_id())
# recursion
self.construct_shortest_path(v.previous, path)
def dijkstra(graph, start, end):
"""
1. adjust the distance of the start and add it to a list of unvisited_vertices "also known as openSet" # noqa:E501
2. get vertices and their indexes from the graph.
3. loop until the len of unvisited_vertices equals 0.
4. pop the first item of the unvisited_vertices and adjust it's visited value, name the item current.
5. loop the neighbors of current, and check if it is already visited
5.1 if not make a new distance equals to current vertex distance+ the cost from current ot next
if this distance is less the distance of the neighbor, assign it to the neighbor instead and
assign previous +current.get_costhortest_path).
note that the dijkstra function steps is slightly more complicated as heaps are used to organize data.
"""
start.set_distance(0)
# 1. create list of start neighbors
# 2. pick least neighbor node
# 3. change distance values of picked node's neighbours
# 4. repeat until list is empty because all else are not connected to start so we dont care # noqa:E501
unvisited_nodes = [vertex for vertex in start.get_neighbors()] # 1 # noqa:E501
# unvisited_nodes.append(start) # the start is assumed to be outer to the graph (not added to it already) # noqa:E501
# heapify the list so the the least distance is at the begining
# print('Before being heapified:', unvisited_nodes)
start.set_visited()
for vertics in unvisited_nodes:
vertics.previous = start
vertics.distance = start.get_cost(vertics)
heapq.heapify(unvisited_nodes)
print(unvisited_nodes)
# import pdb
# pdb.set_trace()
while(len(unvisited_nodes)):
vertics_from_heap = heapq.heappop(unvisited_nodes) # 2 # using heappop instead of pop. # noqa:E501
# print("Heap tuple:", heap_tuple)
# print("Heap vertex:", heap_tuple[1])
# print("the problem is in the line above ... ")
current = vertics_from_heap
print('Current:', current)
current.set_visited()
if current == end:
# current.previous = start
break
for next in current.neighbors:
if next.visited:
continue
tentative_distance = current.get_distance()+current.get_cost(next)
if next not in unvisited_nodes:
heapq.heappush(unvisited_nodes, next)
if tentative_distance < next.get_distance():
next.set_distance = tentative_distance
next.previous = current
# heap rebuild (i don't believe this is a good practice, there should be another way to refresh the heapq) # noqa:E501
# empty the heap
# while(len(unvisited_nodes)):
# heapq.heappop(unvisited_nodes)
# again add vertices unvisited to it
# for v in graph:
# unvisited_nodes.append([v.get_distance(), v])
# heapq.heapify(unvisited_nodes)
# print('Reached the end')
if __name__ == '__main__':
g = Graph()
g.add_vertex('a')
g.add_vertex('b')
g.add_vertex('c')
g.add_vertex('d')
g.add_vertex('e')
g.add_vertex('f')
g.construct_edge('a', 'b', 7)
g.construct_edge('a', 'c', 9)
g.construct_edge('a', 'f', 14)
g.construct_edge('b', 'c', 10)
g.construct_edge('b', 'd', 15)
g.construct_edge('c', 'd', 11)
g.construct_edge('c', 'f', 2)
g.construct_edge('d', 'e', 6)
g.construct_edge('e', 'f', 9)
print('Graph data:', g)
for v in g.vertices_dict.values():
for w in v.get_neighbors():
vid = v.get_id()
wid = w.get_id()
txt = '{}, {}, {}'.format(vid, wid, v.get_cost(w))
print(txt)
dijkstra(g, g.get_vertex('a'), g.get_vertex('e'))
target = g.get_vertex('e')
path = [target.get_id()]
g.construct_shortest_path(target, path)
tx = 'The shortest path:{}'.format(path[::-1])
print(tx)