Я пытаюсь найти кратчайший путь, который проходит через набор узлов [4,7,9] (порядок не нужно сохранять), а затем возвращается к источнику (узел 1). У меня есть набор ребер:
E = [(1, 10), (1, 11), (2, 3), (2, 10), (3, 2), (3, 12), (4, 5), (4 , 12), (5, 4), (5, 14), (6, 7), (6, 11), (7, 6), (7, 13), (8, 9), (8, 13 ), (9, 8), (9, 15), (10, 1), (10, 11), (10, 2), (11, 1), (11, 10), (11, 6), (12, 13), (12, 3), (12, 4), (13, 12), (13, 7), (13, 8), (14, 15), (14, 5), (15 , 14), (15, 9)]
и я попытался адаптировать ответ на Как я могу использовать BFS, чтобы получить путь, содержащий несколько заданных узлов по порядку? , но выдал ошибку:
Traceback (most recent call last):
File "C:/Users/../rough-work.py", line 41, in <module>
graph[edge[0]].link(graph[edge[-1]])
KeyError: 15
Мой адаптированный код выглядит следующим образом:
class Node:
def __init__(self, name):
self.name = name
self.neighbors = []
def link(self, node):
# The edge is undirected: implement it as two directed edges
self.neighbors.append(node)
node.neighbors.append(self)
def shortestPathTo(self, target):
# A BFS implementation which retains the paths
queue = [[self]]
visited = set()
while len(queue):
path = queue.pop(0) # Get next path from queue (FIFO)
node = path[-1] # Get last node in that path
for neighbor in node.neighbors:
if neighbor == target:
# Found the target node. Return the path to it
return path + [target]
# Avoid visiting a node that was already visited
if not neighbor in visited:
visited.add(neighbor)
queue.append(path + [neighbor])
###
n = 15
nodes = list(range(1,n))
E = [(1, 10), (1, 11), (2, 3), (2, 10), (3, 2), (3, 12), (4, 5), (4, 12), (5, 4), (5, 14), (6, 7), (6, 11), (7, 6), (7, 13), (8, 9), (8, 13), (9, 8), (9, 15), (10, 1), (10, 11), (10, 2), (11, 1), (11, 10), (11, 6), (12, 13), (12, 3), (12, 4), (13, 12), (13, 7), (13, 8), (14, 15), (14, 5), (15, 14), (15, 9)]
# Create the nodes of the graph (indexed by their names)
graph = {}
for letter in nodes:
graph[letter] = Node(letter)
print(graph)
# Create the undirected edges
for edge in E:
graph[edge[0]].link(graph[edge[-1]])
# Concatenate the shortest paths between each of the required node pairs
start = 1
path = [graph[1]]
for end in [4,7,9,1]:
path.extend( graph[start].shortestPathTo(graph[end])[1:] )
start = end
# Print result: the names of the nodes on the path
print([node.name for node in path])
В чем может быть проблема с кодом? Я хотел бы расширить граф до произвольно большого числа узлов, больше чем 26 - количество алфавитов (так как я делаю вывод, что предыдущая реализация была только для символьных узлов). Или, если есть более простой способ сделать это, это будет здорово!
Спасибо и некоторая помощь будет высоко оценена!