Я нашел следующую реализацию алгоритма дижксры в python и хочу приспособить его к моей проблеме.Дело в том, что он выдает ошибку при использовании цикла for, хотя я ничего не изменил в коде!
Я хочу сохранить каждую вершину в списке или массиве, получить входную вершину от пользователя в качестве вершины назначения, а затем с помощью цикла for получить все пути от каждой вершины до места назначения и рассчитать их стоимость.Любая помощь будет принята с благодарностью.
Вот код
from collections import deque, namedtuple
# we'll use infinity as a default distance to nodes.
inf = float('inf')
Edge = namedtuple('Edge', 'start, end, cost')
def make_edge(start, end, cost=1):
return Edge(start, end, cost)
class Graph:
def __init__(self, edges):
# let's check that the data is right
wrong_edges = [i for i in edges if len(i) not in [2, 3]]
if wrong_edges:
raise ValueError('Wrong edges data: {}'.format(wrong_edges))
self.edges = [make_edge(*edge) for edge in edges]
@property
def vertices(self):
return set(
sum(
([edge.start, edge.end] for edge in self.edges), []
)
)
def get_node_pairs(self, n1, n2, both_ends=True):
if both_ends:
node_pairs = [[n1, n2], [n2, n1]]
else:
node_pairs = [[n1, n2]]
return node_pairs
def remove_edge(self, n1, n2, both_ends=True):
node_pairs = self.get_node_pairs(n1, n2, both_ends)
edges = self.edges[:]
for edge in edges:
if [edge.start, edge.end] in node_pairs:
self.edges.remove(edge)
def add_edge(self, n1, n2, cost=1, both_ends=True):
node_pairs = self.get_node_pairs(n1, n2, both_ends)
for edge in self.edges:
if [edge.start, edge.end] in node_pairs:
return ValueError('Edge {} {} already exists'.format(n1, n2))
self.edges.append(Edge(start=n1, end=n2, cost=cost))
if both_ends:
self.edges.append(Edge(start=n2, end=n1, cost=cost))
@property
def neighbours(self):
neighbours = {vertex: set() for vertex in self.vertices}
for edge in self.edges:
neighbours[edge.start].add((edge.end, edge.cost))
return neighbours
def dijkstra(self, source, dest):
assert source in self.vertices, 'Such source node doesn\'t exist'
distances = {vertex: inf for vertex in self.vertices}
previous_vertices = {
vertex: None for vertex in self.vertices
}
distances[source] = 0
vertices = self.vertices.copy()
while vertices:
current_vertex = min(
vertices, key=lambda vertex: distances[vertex])
vertices.remove(current_vertex)
if distances[current_vertex] == inf:
break
for neighbour, cost in self.neighbours[current_vertex]:
alternative_route = distances[current_vertex] + cost
if alternative_route < distances[neighbour]:
distances[neighbour] = alternative_route
previous_vertices[neighbour] = current_vertex
path, current_vertex = deque(), dest
while previous_vertices[current_vertex] is not None:
path.appendleft(current_vertex)
current_vertex = previous_vertices[current_vertex]
if path:
path.appendleft(current_vertex)
return path
with open('city1.txt') as fp:
dataset = [line.split() for line in fp.readlines() if line]
for connection in dataset:
connection[2] = int(connection[2])
graph = Graph(dataset)
verteces = []
for set in dataset:
if set[0] not in verteces:
verteces.append(set[0])
if set[1] not in verteces:
verteces.append(set[1])
print(verteces)
destination = input("Enter destination point: ")
verteces.remove(destination)
for vertex in verteces:
print(graph.dijkstra(str(vertex), str(destination)))
, а вот файл
A B 2
A E 2
A W 1
B D 5
B W 4
B C 2
B F 3
C F 7
C V 9
D E 1
D J 7
E K 3
F L 2
F M 7
F R 3
F Y 1
G K 8
G J 5
G H 2
H I 4
H P 1
I K 5
J O 3
J L 2
L N 4
N O 1
O P 1
M N 5
M Z 3
M X 1
Z N 6
X Z 2
Y X 5
R S 4
S V 2
ошибка
File "C:/Users/user/PycharmProjects/dijkstra/main.py", line 122, in <module>
print(graph.dijkstra("A", "B"))
File "C:/Users/user/PycharmProjects/dijkstra/main.py", line 63, in
dijkstra
assert source in self.vertices, 'Such source node doesn\'t exist'
File "C:/Users/user/PycharmProjects/dijkstra/main.py", line 26, in vertices
([edge.start, edge.end] for edge in self.edges), []
TypeError: 'list' object is not callable