Dijkstra's Algorithm¶

Choose the cheapest known next step so a weighted graph reveals the shortest path instead of just any path or the fewest hops.

BFS and DFS explore structure in useful ways, but neither one is enough when edges have different costs. Dijkstra’s algorithm adds a new question: not just where can I go next, but which known route is cheapest so far?

distances = {"A": 0, "B": 4, "C": 2, "D": 7, "E": 7, "F": 4, "G": 6, "H": 5}
closest_node = sorted(distances.items(), key=lambda item: item[1])[0][0]

print("Closest known node:", closest_node)
print("Current best distance to H:", distances["H"])

Closest known node: A
Current best distance to H: 5

Dijkstra keeps expanding the cheapest known route first¶

DFS follows one branch deeply. BFS explores by number of edges. Dijkstra changes the rule again: if edges have weights, the next step should be chosen by smallest accumulated cost, not by depth or by discovery order.

Core Explanation¶

Dijkstra’s algorithm helps compute shortest paths when edges have non-negative weights. It is useful in routing, logistics, delivery optimization, and network planning, where each edge carries a cost such as distance, time, or expense.

Weighted graph intuition

Why BFS is not enough

Why DFS is not enough

A path with fewer edges is not always cheaper. A three-step route can cost less than a direct-looking alternative if each step is inexpensive.

Worked Example and Practice Lab¶

This example shows the core pattern: always process the cheapest known unfinished route next, then relax neighbor distances if a better path is found.

Exercises¶

Explain why Dijkstra needs edge weights while BFS does not.
Describe what float(\"inf\") represents in the setup.
Give one real-world problem where the cheapest route matters more than the fewest steps.
Explain why A -> C -> F -> H beats more expensive alternatives in the example.

Guided Practice¶

What problem does Dijkstra's algorithm solve?¶

Sorting text alphabeticallyThat is unrelated to shortest-path search.

Finding shortest paths in a weighted graph with non-negative edgesCorrect. That is the standard use case.

Counting duplicates in a listThat is not a graph shortest-path problem.

Building a binary search treeThat is a different topic.

What is the shortest distance from `A` to `H` in the example?¶

4That is too small for the available paths.

5Correct. A -> C -> F -> H totals 5.

6There is a cheaper path than 6.

7That is not the best route.

Key Takeaway¶

Dijkstra’s algorithm turns graph exploration into cost-aware decision making: always extend the cheapest known path first when edge weights are non-negative. The larger weighted graph makes that cheapest-path idea visible before you even run the code.