Я реализовал поиск в ширину по псевдокоду в CLRS.
Однако, это не всегда дает мне кратчайший путь между двумя узлами, как вы можете ясно видеть на изображении ниже.
Здесь пошло 10 -> 5 -> 1 -> 6 -> 0, но должно было пройти 10 -> 1 -> 0.
Узлы и ребра:
[[6, 7], [5, 0, 4], [6, 0, 4], [9, 4], [8, 2], [4, 9, 10], [1], [0], [9, 0], [7, 7], [8, 3, 1]]
Расстояния:
[0, 2, 4, 5, 3, 3, 1, 1, 4, 4, 4]
Цвета (2 означает черный):
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
Предшественники:
[None, 6, 4, 10, 1, 1, 0, 0, 4, 5, 5]
Я не могу понять, что здесь происходит, так как мне кажется, что я делаю именно то, что описано в CLRS. В большинстве случаев он идет по правильному пути, но иногда он идет не так по неизвестным причинам. Также есть вероятность, что я просто рисую график неправильно с networkx, я не знаю.
Общая идея заключается в том, что приведенный ниже код генерирует случайные графы, пока не найдет тот, в котором можно нарисовать кратчайший путь между узлами a и b (то есть a и b не являются непересекающимися).
Graph () - мой собственный класс, а nx.Graph () - это функция, отличная от библиотеки networkx.
from collections import deque
import networkx as nx
import matplotlib.pyplot as plt
import random
class Graph(object):
def __init__(self,graph):
self.nodes = graph
self.colors = [0] * len(graph)
self.distances = [len(graph) + 1000] * len(graph)
self.predecessor = [None] * len(graph)
self.queue = deque()
self.nodelist = ['red'] * len(graph)
def BFS(self,start):
self.__init__(self.nodes)
self.colors[start] = 1 #GRAY
self.distances[start] = 0
self.queue.append(start)
while self.queue:
current = self.queue.popleft()
for node in self.nodes[current]:
if self.colors[node] == 0: #WHITE
self.colors[node] = 1 #GRAY
self.distances[node] = self.distances[current] + 1
self.predecessor[node] = current
self.queue.append(node)
self.colors[current] = 2 #BLACK
def draw_path(self,start,end):
self.nodelist[start] = 'green'
previous = end
while previous != start:
self.nodelist[previous] = 'green'
previous = self.predecessor[previous]
print(previous,self.distances[previous])
return
while 1:
try:
graph = []
for i in range(0,15):
t = random.randint(0,3)
if t == 0:
graph.append([random.randint(0,10)])
if t == 1:
graph.append([random.randint(0,10),random.randint(0,10)])
if t == 2:
graph.append([random.randint(0,10),random.randint(0,10),random.randint(0,10)])
x = Graph(graph)
a = 0
b = 10
x.BFS(0)
x.draw_path(a,b)
print(x.nodes)
print(x.distances)
print(x.colors)
print(x.predecessor)
y = nx.Graph()
for i in range(len(graph)):
y.add_node(i)
for i in range(len(graph)):
for j in graph[i]:
y.add_edge(i,j)
graph_label = 'Shortest path from {0} to {1}'.format(a,b)
nx.draw_networkx(y,with_labels=True,node_color=x.nodelist)
plt.title(graph_label)
plt.show()
break
except:
pass