Python BFS 没有给出最短路径

Question

我根据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

Answer 1

题目中提供的图是

[[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，所以路径是正确的，因为它从 end 向后移动到 >开始:

10 <- 5 <- 1 <- 6 <- 0