Python实现Dijkstra算法时遭遇键错误问题求助

Let's break down why you're hitting a Key Error and fix your implementation step by step.

First: The Root Cause of Your Key Error #

Key Errors in your code almost always come from one of two places:

1. You're trying to access a vertex in your distance dictionary L that wasn't initialized.
2. You're referencing a vertex in your graph G that doesn't exist as a key/entry.

Looking at your initialization code:

L = {}
for i in G[0]:
    L[i] = inf
L[start] = 0

This is the first problem. G[0] is almost certainly not the full set of vertices in your graph. For example:

• If G is an adjacency list (a dictionary where keys are vertices), G[0] would only give you the neighbors of vertex 0 (if it exists), not all vertices.
• If G is a list of edges, G[0] is just the first edge in the list, not all unique vertices.

Step 1: Fix the Distance Dictionary Initialization #

You need to make sure L includes every vertex in your graph. Here's how to do it based on common graph structures:

If your graph is an adjacency list (dictionary):

# G looks like {vertex: [(neighbor, weight), ...], ...}
L = {vertex: inf for vertex in G}
L[start] = 0

If your graph is a list of edges:

# G looks like [(v1, v2, weight), ...]
vertices = set()
for edge in G:
    vertices.add(edge[0])
    vertices.add(edge[1])
L = {v: inf for v in vertices}
L[start] = 0

Step 2: Fix the Vertex Selection & Update Logic #

Your pseudocode's step 8 (finding the vertex not in S with the smallest L value) and step 10-14 (updating neighbor distances) can also trigger Key Errors if not implemented correctly. Here's the corrected approach:

from math import inf

def dijkstras(G, start, stop):
    # Initialize distance dict with all vertices
    L = {vertex: inf for vertex in G}
    L[start] = 0
    S = set()

    while stop not in S:
        # Get all vertices not yet processed
        candidates = [v for v in L if v not in S]
        # Handle case where stop is unreachable
        if not candidates:
            return inf
        
        # Pick the vertex with the smallest current distance
        u = min(candidates, key=lambda x: L[x])
        S.add(u)

        # Update distances for u's neighbors (only if neighbor isn't processed)
        for neighbor, weight in G[u]:
            if neighbor not in S:
                if L[u] + weight < L[neighbor]:
                    L[neighbor] = L[u] + weight

    return L[stop]

Step 3: Verify Your Graph Structure #

Double-check that your graph G uses consistent vertex identifiers (e.g., don't mix integers like 0 with strings like "0"). For example, here's a valid adjacency list you can test with:

# Test graph
graph = {
    'a': [('b', 2), ('c', 5)],
    'b': [('a', 2), ('d', 3)],
    'c': [('a', 5), ('d', 1)],
    'd': [('b', 3), ('c', 1)]
}

# Should return 4 (a -> b -> d or a -> c -> d)
print(dijkstras(graph, 'a', 'd'))

Common Key Error Pitfalls to Avoid #

• Mismatched vertex types: If your graph uses integer vertices, don't pass a string as start/stop.
• Missing vertices in G: Ensure every vertex in your graph is a key in the adjacency list (or included in the edge list).
• Unreachable vertices: Add a check for empty candidates to avoid crashes when the stop vertex is unreachable.

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