donnemartin/interactive-coding-challenges · error · ValueError

Invalid start or end node key

Error message

Invalid start or end node key

What it means

Raised by ShortestPath.find_shortest_path when start_node_key or end_node_key is not present in self.graph.nodes. Dijkstra's algorithm in this implementation only knows about nodes seeded into the priority queue at construction time, so an unknown endpoint cannot be processed and the code raises ValueError to signal a validly-typed but semantically invalid key.

Source

Thrown at graphs_trees/graph_shortest_path/graph_shortest_path_solution.ipynb:204

    "        self.graph = graph\n",
    "        self.previous = {}  # Key: node key, val: prev node key, shortest path\n",
    "        self.path_weight = {}  # Key: node key, val: weight, shortest path\n",
    "        self.remaining = PriorityQueue()  # Queue of node key, path weight\n",
    "        for key in self.graph.nodes.keys():\n",
    "            # Set each node's previous node key to None\n",
    "            # Set each node's shortest path weight to infinity\n",
    "            # Add each node's shortest path weight to the priority queue\n",
    "            self.previous[key] = None\n",
    "            self.path_weight[key] = sys.maxsize\n",
    "            self.remaining.insert(\n",
    "                PriorityQueueNode(key, self.path_weight[key]))\n",
    "\n",
    "    def find_shortest_path(self, start_node_key, end_node_key):\n",
    "        if start_node_key is None or end_node_key is None:\n",
    "            raise TypeError('Input node keys cannot be None')\n",
    "        if (start_node_key not in self.graph.nodes or\n",
    "                end_node_key not in self.graph.nodes):\n",
    "            raise ValueError('Invalid start or end node key')\n",
    "        # Set the start node's shortest path weight to 0\n",
    "        # and update the value in the priority queue\n",
    "        self.path_weight[start_node_key] = 0\n",
    "        self.remaining.decrease_key(start_node_key, 0)\n",
    "        while self.remaining:\n",
    "            # Extract the min node (node with minimum path weight)\n",
    "            # from the priority queue\n",
    "            min_node_key = self.remaining.extract_min().obj\n",
    "            min_node = self.graph.nodes[min_node_key]\n",
    "            # Loop through each adjacent node in the min node\n",
    "            for adj_key in min_node.adj_nodes.keys():\n",
    "                # Node's path:\n",
    "                # Adjacent node's edge weight + the min node's\n",
    "                # shortest path weight\n",
    "                new_weight = (min_node.adj_weights[adj_key] +\n",
    "                    self.path_weight[min_node_key])\n",
    "                # Only update if the newly calculated path is\n",
    "                # less than the existing node's shortest path\n",

View on GitHub (pinned to 358f2cc604)

Solutions

1. Verify both keys with `key in graph.nodes` (or ShortestPath.path_weight) before calling find_shortest_path
2. Re-instantiate ShortestPath after adding nodes to the graph so its queue includes them
3. Normalize key types consistently (e.g., always str(key) or always int) at graph-build and query time

Example fix

# before
sp.find_shortest_path('a', 'z')  # ValueError if 'z' was never added

# after
if start in graph.nodes and end in graph.nodes:
    sp.find_shortest_path(start, end)

if start in graph.nodes and end in graph.nodes:
    sp.find_shortest_path(start, end)
else:
    handle_missing_endpoint(start, end)

def keys_in_graph(graph, *keys):
    return all(k in graph.nodes for k in keys)

try:
    sp.find_shortest_path(start, end)
except ValueError as e:
    if 'Invalid start or end node key' in str(e):
        handle_missing_endpoint(start, end)
    else:
        raise

When it happens

Trigger: Calling find_shortest_path on a key never added via graph.add_node/add_edge; using a key with a different type than stored (e.g., '1' vs 1); running shortest path on a graph built after ShortestPath was instantiated, so the object never saw the new nodes.

Common situations: Type mismatches between string IDs from input data and integer keys in the graph; forgetting that ShortestPath snapshots graph.nodes at __init__ and does not track later insertions; typos or stale keys after nodes are removed.

Related errors

• Invalid key
• neighbor not found
• Invalid key
• graph cannot be None
• Input node keys cannot be None

AI-assisted analysis of donnemartin/interactive-coding-challenges@358f2cc604 (2026-08-28). Data as JSON: /api/errors/7e1f1764b49adf53. Report an issue: GitHub.