How does Dijkstra's algorithm work?

Question presented to candidate: "Explain how Dijkstra's algorithm finds shortest paths in a weighted graph, then implement it in Python for a graph given as an edge list. What is its complexity, and when does it give the wrong answer?"

What a strong answer should cover:

• The greedy rule: repeatedly settle the unsettled node with the smallest tentative distance, then relax its outgoing edges.
• Edge relaxation, dist initialised to infinity except the source, and a parent array to rebuild the route.
• A min-heap of (distance, node) tuples with heapq, and lazy deletion: push a new entry on every improvement and skip stale entries when popped, because heapq has no decrease-key.
• O((V + E) log V) time with a binary heap, O(V + E) space; why non-negative weights are required (and what to use instead).
• Python specifics: float("inf") for unreachable, tuples compare element by element so ties fall back to the node, and that node must be comparable.

Clarifying questions expected:

• "Can weights be negative, and is the graph directed?"
• "Do you need the route itself, or only the distance? What should unreachable nodes return?"

Code / implementation expected: Yes — a Python dijkstra(n, edges, source) using heapq, returning distances (and ideally parents for the path).