Can edge weights be zero?

Yes. Nonnegative includes zero.

Can it work on an undirected graph?

Yes; each connection can be traversed in either direction.

Does it need a heuristic estimate to the goal?

No. Goal-directed estimates are associated with methods such as A*.

Can several shortest paths exist?

Yes. A routine may return one of several equal-cost paths.

AI Glossary / Graphs and symbolic AI / Advanced

Dijkstra's algorithm

Definition

Dijkstra's algorithm finds minimum-total-cost paths from a starting node in a weighted graph whose edge weights are nonnegative. It repeatedly confirms the unprocessed node with the smallest known distance and improves estimates for its neighbors. It can compute distances to all reachable nodes or stop after confirming a specified destination.

What it means

Shortest means lowest sum of edge weights, which need not mean fewest edges or smallest geographic distance. A graph can represent travel distance, an additive processing cost, or another suitable nonnegative quantity.
The algorithm answers a graph question precisely under its assumptions. It does not establish that the graph includes every real constraint or that its weights predict changing conditions accurately. A mathematically shortest route can still be unsuitable if an important restriction was omitted from the representation.

How it works

Assign the source distance zero and other nodes an initially unknown, effectively infinite distance. Keep tentative distances for nodes reached during the search. Select the unsettled node with the smallest tentative distance and settle it: its distance is now final under the nonnegative-weight assumption.
For each permitted outgoing edge, compare the neighbor's existing estimate with the settled distance plus that edge's cost. If the new route is cheaper, update the estimate and its predecessor. This operation is called relaxation. Predecessor links allow reconstruction of a path after its cost has been found.
A priority queue can organize the next selection. Performance depends on the graph representation and queue implementation. If only one destination matters, stop when that destination is settled, not when it is first discovered. Nodes that cannot be reached from the source do not acquire a finite path. Directed edges must be followed in their permitted direction.

Three practical examples

Route planning: A service finds a minimum-distance route through a road graph with nonnegative lengths. One-way restrictions belong in the graph. Time-dependent congestion requires a suitable model rather than an assumption that static lengths capture travel time.
Workflow design: An analyst models permitted transitions and additive processing costs. The algorithm can find a least-cost transition sequence if the representation captures the relevant state. Capacity constraints or costs depending on earlier choices may require a richer model.
Network analysis: A team measures shortest weighted connections from one node to the rest of a network. The resulting distances describe the selected cost measure. They should not automatically be interpreted as reliability, information quality, or causal influence.

Think of it this way

Imagine expanding a frontier in order of total cost already paid from the starting point. The next location confirmed is the cheapest pending one overall. This differs from repeatedly choosing the cheapest edge leaving the current location, which can lead to an expensive overall route.

Worked example

Use a directed graph with five edges: S to A costs 4, S to B costs 1, B to A costs 2, A to G costs 3, and B to G costs 8. There are no other edges. Start at S and seek G.
Settle S at cost 0. Its outgoing edges give tentative distances A = 4 and B = 1. Next settle B because 1 is the smallest pending distance. Through B, the route to A costs 1 + 2 = 3, improving A's estimate from 4 to 3. The route to G costs 1 + 8 = 9, so G is discovered with estimate 9.
Do not stop yet. A still has the smaller pending distance 3. Settle A and relax its edge to G: the new candidate cost is 3 + 3 = 6, improving G from 9 to 6. Settle G at 6 and stop. Following predecessors yields S-B-A-G, whose edge costs sum to 1 + 2 + 3 = 6.
The first discovered route to G cost 9; the confirmed shortest route costs 6. An isolated node U would remain unreachable from S.
For a separate caution, consider S to A costing 2, S to B costing 5, and B to A costing -4. Settling A at 2 would be premature because S-B-A costs 1. This negative-edge example violates the algorithm's assumptions even though it contains no cycle. A different suitable shortest-path method is needed.

Illustrative case study

Fictional Willow Routing builds an internal route-comparison tool. Its initial implementation returns as soon as the destination appears among a node's neighbors. Small examples reveal that another pending node can still lead to a cheaper destination route.
The team changes termination to occur when the destination is selected with the smallest current tentative distance. It checks directed connections, unreachable destinations, and the meaning of each edge cost. It also rejects unsupported negative costs instead of silently treating them as ordinary distances.
This fictional scenario illustrates correctness checks around an implementation.

Common misconceptions and mistakes

“Shortest means fewest edges.” It means the smallest sum of the specified weights.
“The first route found is optimal.” A tentative destination distance can still improve.
“Negative edges are harmless without negative cycles.” They can invalidate the settling rule.
“The next choice is the cheapest outgoing edge.” The algorithm selects the smallest total tentative distance across pending nodes.
“Any shortest-path tree is a minimum spanning tree.” These solve different optimization problems.

Business use

Define the graph's state, permitted movements, and cost units before choosing the algorithm. Check whether costs are additive and nonnegative, and whether they remain appropriate during a query. Requirements depending on history may need to be represented in the state itself.
Test route costs and reconstructed paths together. Include unreachable nodes and competing alternatives that improve a destination after discovery. Consider numerical precision when costs are accumulated, and distinguish errors in the implementation from inaccurate input data.

Check your understanding

Why is B settled before A?

Answer: Its tentative distance is 1 rather than 4.

Why is G's first estimate not final?

Answer: A remains pending with a cheaper total distance and can improve the route to G.

What is the final route cost?

Answer: Six, along S-B-A-G.

Related terms

Shortest Paths
Priority queue
Shortest path
edge relaxation
predecessor
nonnegative weight
Bellman-Ford algorithm
A* search

Learn next

Trace tentative distances on a small graph after every relaxation. Compare stopping at first discovery with stopping at settlement, then change one edge to a negative value and identify which correctness assumption fails.

Sources

NIST Dictionary of Algorithms and Data Structures, Dijkstra's algorithm: https://xlinux.nist.gov/dads/HTML/dijkstraalgo.html MIT 6.006, Dijkstra lecture notes: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/6277a1f06100c26a7ff21031af6757b5_MIT6_006F11_lec16.pdf MIT 6.006, single-target stopping rule: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/b2d98a9d28eca2c0dce89757bea893ae_MIT6_006F11_lec18.pdf NetworkX, weighted single-source Dijkstra reference: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.single_source_dijkstra.html

Previous: Digitization Next: Dimensional fact model