Uniform Cost Search (Dijkstra) Calculator

Read the Theory Guide →

Build a weighted graph, choose a start and a goal, and calculate the cheapest path with a step-by-step priority queue matrix. Change edge costs or direction and recalculate to see how tentative costs and the final route respond.

What You Can Explore

  • Build a weighted graph on the canvas, or edit the preloaded one by adding nodes and assigning costs to edges.
  • Switch between directed and undirected graphs, and choose any Starting Point and Goal Point.
  • Change an edge cost and press Calculate Dijkstra Matrix to see how the route and accumulated costs change.
  • Read the priority queue matrix, calculation breakdown, and shortest costs to all reachable nodes to trace the search.
Core Mechanics
▼
  • Always Pop the Cheapest: Dijkstra runs on a Priority Queue. Instead of popping the oldest or newest node, you must always pop the unvisited node with the lowest cumulative cost, g(n)g(n).
  • Edge Relaxation: When evaluating neighbors, calculate the running total from the start. If this new total is cheaper than a neighbor's currently known cost, you relax the edge by updating it with the better score.
  • Settled Nodes Are Locked: Once a node is popped as the absolute cheapest option, its shortest path is mathematically guaranteed. Lock it in the Closed List and never evaluate it again.
  • The Goal Test (Pop, Don't Peek): Do not declare victory the moment the goal node appears in the queue! You must wait until the goal is officially popped to guarantee no cheaper path to it exists.
Initializing Workspace...

Understanding Your Result

The matrix, calculations, and path all come from the graph and start node you entered. The summary shows the cheapest route to your selected goal, while the matrix and final cost list show how the search established the cheapest known cost to each reachable node.

  • Total Path Cost is the cost of the cheapest route from your selected start to your selected goal. The solver also records the cheapest known cost to every other reachable node.
  • In the matrix, highlighted cells show cost updates, the outlined cell marks the node selected for the next step, and dashes indicate nodes that have already been closed. Use the legend above the matrix to interpret each state.
  • The Calculation Breakdown shows how each neighbor was evaluated. A relaxed neighbor received a lower path cost, while a skipped neighbor already had an equal or cheaper known cost.
  • If a node remains unreachable, there is no allowed path from the selected start to that node. In a directed graph, check the direction of the edges before assuming that a visible connection can be followed.

Try These Experiments

Cheapen the Edge from A to E

Setup: Run the preloaded graph with A as the start and D as the goal, and note the Total Path Cost and route shown in the result.

Action: Change the cost of the edge from A to E from 5 to 2, then press Calculate Dijkstra Matrix again.

What to Observe: The cheapest route changes from A → B → C → D to A → E → C → D, and the Total Path Cost falls from 9 to 6. In the matrix and calculation breakdown, follow how the lower cost through E reaches C and then D.

Takeaway: A lower edge cost can change which route becomes cheapest. Because Dijkstra accumulates the cost paid so far, a change early in a route can affect the costs of nodes reached later.

Improve a Tentative Cost

Setup: Use the preloaded graph with A as the start and D as the goal, and watch how D first receives a cost through one route before a cheaper route is discovered.

Action: Add a direct edge from A to D with a cost of 15, then run the calculation again.

What to Observe: Follow the D column in the matrix. D first receives the tentative cost 15 from A, then receives the lower cost 9 through C. The breakdown shows both calculations before D is selected.

Takeaway: A node's first known cost is not necessarily its cheapest cost. Dijkstra can replace a tentative cost when a cheaper route is discovered before that node is closed.

Start From a Different Node

Setup: Keep the preloaded graph and the goal D, then change the Starting Point from A to B.

Action: Run the calculation with the graph directed, then switch it to undirected and run it again.

What to Observe: In the directed run, nodes that cannot be reached by following the edge directions remain unreachable, while D is reached with a cost of 5. In the undirected run, the previously one-way connections can be followed in either direction, making every node reachable.

Takeaway: Dijkstra only considers edges that can actually be followed from the current node. Changing the starting point or edge direction can therefore change both which nodes are reachable and the cheapest costs found for them.