Dijkstra's Algorithm in Google Sheets

Project for Discrete Mathematics Course

Fall 2019
generating the distances to every cell

finding the shortest path using the distance map

After implementing a couple shortest path algorithms in MATLAB for my Discrete Mathematics course, I decided to try to implement Dijkstra's Algorithm in Google Sheets. I managed to do it without scripting by basically creating a cellular automaton. The formula in each cell looks at the values of all its neighbors, then sets its value to the smallest of its neighbors plus one. When the values of all the cells settle, a map has been generated with the distances of all the cells from the starting cell.

To generate the path from this map, another cellular atomaton works backward from the target cell. The target cell adds itself to a "path" map, and any cell whose value is one less than a neighbor cell in "path" adds itself to "path".

Feel free to clone my spreadsheet and play with it here.

distances to cells from starting cell shortest path between starting and target cells
Contact Info
Feel free to contact me!

© 2020 Rowan Sharman      CSS by w3.css