Meaning and mechanism
The graph represents positions as vertices, and movable relationships as edges. The cost of a path is defined as the sum of the costs of the edges traversed or the costs assigned to each vertex.
Width-first search expands based on the number of moves on edges with equal costs. Dijkstra’s algorithm selects candidates based on the current minimum accumulated cost.
Relationships and conditions
Relaxation updates d(v) to min(d(v),d(u)+w(u,v)). When a cheaper path is found, both the distance and predecessor information are updated.
The standard procedure for Dijkstra’s algorithm relies on the condition that there are no negative weights. The experiment uses only up, down, left, and right movements, with positive costs, while diagonal or actual road restrictions are omitted.
What to observe in the simulation
BFS minimizes steps; Dijkstra minimizes total cost.
Moves are orthogonal and costs positive. Reproducible presets set walls and endpoints.
Key relationships and symbols
d(v) = min[d(u) + w(u,v)]
| Symbol | Meaning | Unit |
|---|---|---|
| d(v) | Current distance estimate from the start to v | Cost |
| w(u,v) | Cost of moving from u to v | Cost |
Worked example
With equal costs, how do the shortest distances compare?
Equal · BFS minimizes steps; Dijkstra minimizes total cost.
Common misconceptions
- It is not the case that width-first search minimizes the cost for all graphs with different edge weights.