寻找自定义BFS最短路径算法（bfsVisit）的反例

我在复习Dijkstra算法时，自己编写了一个基于BFS思想的最短路径算法bfsVisit。我知道这个算法理论上不应该正确——它的时间复杂度为O(V+E)，比Dijkstra算法更优，但试了多个测试用例，它和正确的Dijkstra算法输出完全一致，始终找不到反例。

以下是两个算法的实现代码：

from typing import List, Dict
from heapq import heappush, heappop
from collections import deque

def bfsVisit(graph: List[Dict[int, float]], source: int)->List[float]:
    """
    :param graph: adjacency list representation of graph
    :param source: source node
    :return: distance from source to all other nodes
    """
    n = len(graph)
    distance = [float('inf')] * n
    distance[source] = 0
    toExplore = deque([source]) 
    explored = [False] * n
    while toExplore:
        u = toExplore.popleft()
        if explored[u]:
            continue
        explored[u] = True
        for v, weight in graph[u].items():
            tempDist = distance[u] + weight
            if tempDist < distance[v]:
                distance[v] = tempDist
                toExplore.append(v)
    return distance

def dijkstra(graph: List[Dict[int, float]], source: int)->List[float]:
    """
    :param graph: adjacency list representation of graph
    :param source: source node
    :return: distance from source to all other nodes
    """
    n = len(graph)
    distance = [float('inf')] * n
    distance[source] = 0
    toExplore = [(0, source)]
    while toExplore:
        dist, u = heappop(toExplore)
        if dist > distance[u]:
            continue
        for v, weight in graph[u].items():
            tempDist = dist + weight
            if tempDist < distance[v]:
                distance[v] = tempDist
                heappush(toExplore, (tempDist, v))
    return distance

目前两个算法均通过了以下测试用例：

from pytest import fixture, mark
from pytest_lazyfixture import lazy_fixture
from dijkstra import dijkstra, bfsVisit

@fixture
def graph1():
    graph = [None for _ in range(6)]
    graph[0] = {1: 1, 3: 4, 4: 2}
    graph[1] = {2: 3, 3: 1}
    graph[2] = {}
    graph[3] = {2: 1, 5: 2}
    graph[4] = {3: 2, 5: 3}
    graph[5] = {}
    return graph

@fixture
def graph2():
    graph = [None for _ in range(6)]
    graph[0] = {1: 1, 3: 4, 4: 2}
    graph[1] = {2: 3, 3: 1}
    graph[2] = {5:1}
    graph[3] = {2: 1}
    graph[4] = {3: 2, 5: 3}
    graph[5] = {}
    return graph

@fixture
def graph3():
    graph = [None for _ in range(3)]
    graph[0] = {1: 1, 2: 3}
    graph[1] = {2: 3}
    graph[2] = {}
    return graph

@mark.parametrize('graph, expected', 
                  [(lazy_fixture('graph1'), [0, 1, 3, 2, 2, 4]), 
                   (lazy_fixture('graph2'), [0, 1, 3, 2, 2, 4]),
                   (lazy_fixture('graph3'), [0, 1, 3])])
class TestShotestPath:
    def test_dijkstra(self, graph, expected):
        assert dijkstra(graph, 0) == expected
    
    def test_bfsVisit(self, graph, expected):
        assert bfsVisit(graph, 0) == expected

反例构造与分析 #

我们可以构造这样一个图：

def graph_counterexample():
    graph = [None for _ in range(4)]
    graph[0] = {1: 3, 2: 1}  # 0到1权重3，0到2权重1
    graph[1] = {3: 1}         # 1到3权重1
    graph[2] = {1: 1, 3: 5}   # 2到1权重1，2到3权重5
    graph[3] = {}              # 3无出边
    return graph

预期结果

从节点0出发，各节点的最短路径距离应为：

• 0: 0
• 1: 0→2→1，总长度2
• 2: 1
• 3: 0→2→1→3，总长度3

算法对比结果

• Dijkstra算法输出：[0, 2, 1, 3]，符合预期
• bfsVisit算法输出：[0, 2, 1, 4]，与预期不符

原因分析

bfsVisit的问题出在节点标记为explored后就不再处理的逻辑：

1. 初始队列加入节点0，弹出后处理邻居1和2，将它们加入队列，此时distance[1]=3，distance[2]=1
2. 队列弹出节点1，标记为explored，处理邻居3，设置distance[3]=3+1=4并加入队列
3. 队列弹出节点2，标记为explored，更新distance[1]为1+1=2并将1重新加入队列；同时发现到3的路径1+5=6大于当前distance[3]，不更新
4. 队列弹出节点3，标记为explored，无后续处理
5. 队列弹出节点1，但此时explored[1]已经为True，直接跳过，不会处理它的邻居3——导致distance[3]无法更新为2+1=3

而Dijkstra算法通过优先队列每次选择当前距离最短的节点处理，即使节点1被重新加入队列，只要新的距离更短，就会重新处理它的邻居，从而得到正确的结果。

内容的提问来源于stack exchange，提问作者Tianshu Yu