{{ summaryTitle }}
{{ summaryValue }}

{{ summaryLine }}

Moves: {{ resultsReady && computation.values.found ? computation.values.route_moves : '—' }} Visited: {{ resultsReady ? computation.values.visited_count : '—' }} Movement: {{ resultsReady ? movementLabel : '—' }}
Choose the frontier rule to compare on the same grid.
Diagonal movement uses geometric distance before applying terrain weight.
Used only for eight-way movement; the selection remains shareable when four-way is active.
Choose a tool, then activate a cell in the grid.
Grid presets:
Presets replace terrain and endpoints without changing the algorithm or movement rules.
Start Goal Wall Frontier Visited Route

{{ traceStatusLine }}

A presentation-only refinement; opening Advanced does not alter the route.
Route report
{{ row.label }}
{{ row.display }}
{{ routeReportHeading }}

{{ routeInterpretation }}

{{ algorithmCaveat }}

The chart renderer is unavailable. The same step counts remain in the decision ledger.

StepCurrentFrontierVisitedDecisionCopy
{{ row.step }}{{ row.current }}{{ row.frontier }}{{ row.visited }}{{ row.decision }}
Directed Graph Algorithms Simulator Trace topological ordering and cycle evidence or find strongly connected components with four classic directed-graph algorithms step by step.
Minimum Spanning Tree Algorithm Simulator Compare Kruskal and Prim on weighted graphs with deterministic edge decisions, cycle rejections, and minimum spanning forest results.
Network Flow Algorithm Simulator Simulate Edmonds-Karp or Dinic on an editable capacity network and verify the maximum flow with residual traces and a minimum-cut certificate.
Dynamic Programming Algorithm Simulator Explore memoization and tabulation for three classic problems through state tables, exact recurrences, and traceable solution choices.

Finding a route is not always the same as finding the cheapest route. On an open grid, a short path may be obvious. Once walls, difficult terrain, diagonal movement, and blocked corners are added, the search rule decides which cells are explored first and what kind of result can be guaranteed.

A pathfinding search maintains a frontier of discovered cells that have not yet been expanded. Breadth-first search (BFS) takes the oldest frontier cell, depth-first search (DFS) takes the newest, Dijkstra chooses the lowest accumulated cost, and A* combines accumulated cost with an estimate of the remaining distance. That difference changes the exploration pattern even when several algorithms eventually reach the same goal.

Algorithm Frontier choice Safe conclusion
BFS Oldest discovered cell Fewest moves when every permitted move has equal cost.
DFS Most recently discovered cell Demonstrates deep exploration; it does not promise the shortest or cheapest route.
Dijkstra Lowest accumulated cost Lowest-cost route when movement costs are non-negative.
A* Lowest accumulated cost plus a goal estimate The same lowest-cost goal with a compatible non-overestimating heuristic.

Grid movement also changes cost. A cardinal move travels one cell width. A diagonal move travels the square root of two cell widths before the destination terrain weight is applied. Preventing corner cutting forbids a diagonal when either adjoining cardinal cell is blocked, which avoids slipping through the touching corners of two walls.

A route is only optimal for the selected grid and rules. Weighted terrain is a teaching cost, not travel time or geographic distance, and the number of visited cells is not a wall-clock benchmark. A no-route result means the frontier became empty under the current walls, endpoints, movement, and corner policy.

How to Use This Tool:

Build or load a grid before choosing the movement rules and search algorithm you want to compare.

  1. Start with Weighted detour, Open grid, or No path, or edit the 6 by 10 grid with the Cell tool. Walls block movement; weights 2 and 5 increase the cost of entering a cell.
  2. Choose Breadth-first search, Depth-first search, Dijkstra, or A* according to the behavior you want to study.
  3. Set Movement to four-way or eight-way. For eight-way movement, decide whether Diagonal corners may be crossed.
  4. Use the trace controls to step through expanded cells and frontier changes. Playback interval changes animation timing only; it does not change the route or search order.
  5. Check Route report for outcome, moves, weighted cost, and visited cells, then use Decision ledger to inspect the deterministic expansion order.

Interpreting Results:

Read Weighted cost and Route moves separately. A path with more moves can cost less when it avoids weight-5 cells. BFS can minimize the move count while missing the lowest weighted cost, and DFS may return a longer or more expensive path simply because of its depth-first order.

The Visited cells count describes this deterministic run on this grid. It can compare search breadth when the grid, endpoints, movement, and corner policy stay fixed, but it does not measure runtime or prove that one algorithm is universally faster.

For a No route result, verify the wall pattern and diagonal policy before concluding that the goal is isolated. A single blocked adjoining cell can remove a diagonal when corner cutting is prevented.

Technical Details:

Each open cell is a graph vertex. Permitted cardinal or diagonal moves form edges, and the cost of an edge is its geometric distance multiplied by the destination cell's terrain weight. Walls create no destination edge.

Formula Core:

For a route containing moves from cell vi-1 to vi, total route cost adds the distance of each move multiplied by the terrain weight of the cell entered.

C= ∑ i=1 m d(vi-1,vi) ×w(vi)

Cardinal distance is 1 and diagonal distance is √2. Open cells have weight 1; weighted cells have weight 2 or 5. The displayed cost is rounded to at most six decimal places in the canonical result and shown more compactly in the interface.

Rule Core:

Mode Priority rule Cost handling
BFS First in, first out Terrain affects the reported path cost but not frontier order.
DFS Last in, first out Terrain affects the reported path cost but not frontier order.
Dijkstra Smallest accumulated cost g A cheaper discovery replaces a more expensive route to the same cell.
A* Smallest g + h h is Manhattan distance for four-way movement and octile distance for eight-way movement.

Neighbor order is deterministic: north, east, south, west, followed by the four diagonals for eight-way movement. Equal priorities are resolved by discovery order and then cell index. This makes repeated runs comparable when every input remains unchanged.

A* uses a minimum terrain weight of 1 in its Manhattan or octile estimate, so the estimate does not exceed the remaining cost in this model. Dijkstra and A* therefore minimize the same non-negative movement cost. BFS has a fewest-move guarantee only when all allowed moves count equally, and DFS has no optimality guarantee.

Worked Examples:

Avoiding an expensive neighbor

Place the start at R1C1, the goal at R2C2, and a weight-5 cell at R1C2. With four-way movement, Dijkstra goes through R2C1 and reaches the goal in two moves with cost 2. The direct-looking route through R1C2 would cost 6, so the extra cost matters more than visual proximity.

References: