Dijkstras Demo

Created by Jeremy Lane for Combinatorics (Math 3134 at VT)

How this works:
This simulates Dijkstra algorithm on a grid.
Use the tools on the right to build or erase walls.
Step through the program or auto play with the player on the bottom right.

Dijkstra algorithm strategy:
Starting from the start point (green circle), the start point attempts to adopt its neighbors. Cells that haven't been adopted become adopted and gain a Total Cost (TC) equal to the their cost. These newly adopted cell get the arrowhead symbol and seek to adopt all their neighbors. Cells that become parents become a line, which connects its new child to its parent.

Following the line backwards shows the path of parentage to the starting point.
When a cell adopts another cell, it adds its TC to the cost of the potential child to get the childs new TC.
If the child already has been adopted, it compares the new TC to the existing TC, preferring the lowest TC.

If a cell has no neighbors it can adopt, it gets the red circle symbol, indicating a dead end. This continues, using BFS, until a path is found to the end point (magenta circle) or all accessible cells are reached.