Python BFS 没有给出最短路径
Python BFS not giving the shortest path
我已经根据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() 是我自己的 class 而 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
题目中提供的图表是
[[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 而不是 10,路径是正确的,因为它从 结束向后移动 到 开始:
10 <- 5 <- 1 <- 6 <- 0
我已经根据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() 是我自己的 class 而 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
题目中提供的图表是
[[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 而不是 10,路径是正确的,因为它从 结束向后移动 到 开始:
10 <- 5 <- 1 <- 6 <- 0