带权有向图的BFS：为何无法得到最短路径？

Great question! BFS works flawlessly for unweighted graphs because it explores nodes level by level, assuming every edge has the exact same "cost." But throw weighted edges into the mix, and it can easily miss the true shortest path. Let’s prove this with a tiny, intuitive graph and straightforward Python code.

The Test Graph #

We’ll use a super simple 3-node graph to highlight the issue:

• Node A connects to Node B with a weight of 5
• Node A connects to Node C with a weight of 1
• Node C connects to Node B with a weight of 1

The actual shortest path from A to B is A -> C -> B (total weight: 1 + 1 = 2), but BFS will prioritize the direct A->B edge because it’s a first-level neighbor, completely ignoring the cheaper two-step route.

The Code Demo #

from collections import deque

# Define our weighted graph as an adjacency list
weighted_graph = {
    'A': [('B', 5), ('C', 1)],
    'B': [],
    'C': [('B', 1)]
}

def bfs_path_finder(graph, start, end):
    """Basic BFS implementation that returns the first discovered path (ignores weights)"""
    queue = deque()
    queue.append([start])
    visited = set()
    
    while queue:
        current_path = queue.popleft()
        current_node = current_path[-1]
        
        if current_node == end:
            return current_path
        
        if current_node not in visited:
            visited.add(current_node)
            # Add all neighbors to queue (BFS doesn't consider edge weights here)
            for neighbor, _ in graph[current_node]:
                new_path = current_path.copy()
                new_path.append(neighbor)
                queue.append(new_path)
    
    return None  # No path exists between start and end

def calculate_total_weight(graph, path):
    """Calculate the total weight of a given path in the graph"""
    total_weight = 0
    for i in range(len(path)-1):
        current = path[i]
        next_node = path[i+1]
        # Find the weight between current and next node
        for neighbor, weight in graph[current]:
            if neighbor == next_node:
                total_weight += weight
                break
    return total_weight

# Run BFS to get its "shortest" path
bfs_result = bfs_path_finder(weighted_graph, 'A', 'B')
bfs_total = calculate_total_weight(weighted_graph, bfs_result)

# The actual shortest path (we can also use Dijkstra's to find this programmatically)
true_shortest_path = ['A', 'C', 'B']
true_total = calculate_total_weight(weighted_graph, true_shortest_path)

# Print results
print(f"BFS found path: {' -> '.join(bfs_result)} | Total weight: {bfs_total}")
print(f"Actual shortest path: {' -> '.join(true_shortest_path)} | Total weight: {true_total}")

What You’ll See When Running This #

Execute the code, and you’ll get output like this:

BFS found path: A -> B | Total weight: 5
Actual shortest path: A -> C -> B | Total weight: 2

This makes it crystal clear: BFS picks the direct (but far heavier) path first because it only counts the number of edges, not their weights. For weighted graphs, algorithms like Dijkstra’s or Bellman-Ford are built to account for edge weights and find the true shortest path.

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