Computer Science Canada Dijkstra's Algorithm... With Excel!

 Author: Sane [ Tue May 13, 2008 9:41 pm ] Post subject: Dijkstra's Algorithm... With Excel! I implemented Dijkstra's Algorithm purely in Excel today! Without any Macros or Visual Basic either. I did this in Data Management class out of boredom. It works purely through Excel's cell referencing, to generate the min-heap and update the distances for each iteration, all in several large tables. It uses only the most basic Excel functions, such as min(), if(), and(), and or(). The complexity comes in the logic of Dijkstra's algorithm and properly cell referencing to avoid cyclical cell references. It's demonstrated with a 12x12 maze that you can change by replacing the cells with 1 or nothing, and moving around "Start" and "Exit". It will calculate the shortest path to the exit by running Dijkstra's Algorithm on 7 worksheets, and displaying the path back onto the original worksheet. Even though the edges are of uniform weight, I decided not to use a BFS because I figured implementing a priority queue in Excel is easier than a normal queue. The maze is limited to a certain size because this was just a couple hours of work. Didn't want to get too out of hand by making it dynamic. I've zipped and attached the complete .xls file if anyone's interested. To delete a wall, click the block and hit "Delete". To add a wall, click an empty square and type "1" then "Enter". To change the Start and Exit, it should be obvious what to do. Remember it's limited to 12x12. Below is a screenshot of it in action:

 Author: nike52 [ Tue May 13, 2008 10:13 pm ] Post subject: Re: Dijkstra's Algorithm... With Excel! wooah that's awesome !

 Author: md [ Wed May 14, 2008 12:18 am ] Post subject: RE:Dijkstra\'s Algorithm... With Excel! you clearly have WAY too much time on your hands... but awesome none the less.

 Author: james3177 [ Thu Aug 20, 2009 5:11 pm ] Post subject: Re: Dijkstra's Algorithm... With Excel! Very cool application. I have been playing with it trying to figure out how to change it from a 12x12. I have had no luck though. I think I am having a circular refrence problem. What steps should I do to change the grid size? Thanks for your time

 Author: andrew. [ Thu Aug 20, 2009 6:51 pm ] Post subject: RE:Dijkstra\'s Algorithm... With Excel! It's truly amazing what you can do with Excel. Good job man. +Bits

 Author: saltpro15 [ Fri Aug 21, 2009 10:52 am ] Post subject: RE:Dijkstra\'s Algorithm... With Excel! "There are no coincidences, only the illusion of coincidence" - V for Vendetta really cool btw Sane

 Author: andrew. [ Fri Aug 21, 2009 11:12 am ] Post subject: RE:Dijkstra\'s Algorithm... With Excel! Just a weird coincidence (if you believe in coincidences).

 Author: Tony [ Fri Aug 21, 2009 11:46 am ] Post subject: Re: Dijkstra's Algorithm... With Excel! Sane @ Fri Aug 21, 2009 10:32 am wrote:and hadn't thought about it or even came to compsci.ca for a moment since then... I hope you have learned your lesson about leaving compsci.ca for extended periods of time Also, you guys might be interested in this awesome Demoscene ( http://en.wikipedia.org/wiki/Demoscene ) done in Excel -- http://www.youtube.com/watch?v=HZ6Q224UPkc

 Author: james3177 [ Fri Aug 21, 2009 2:44 pm ] Post subject: Re: Dijkstra's Algorithm... With Excel! Just a coincidence. I am from southern california, was looking for an example using Dijkstra's algorithm and found your excel sheet. I played around with it for hours with no luck so I put a reply. Ill try to use the link you posted. Thanks for the reply.

 Author: aldus [ Sun Apr 29, 2012 4:52 am ] Post subject: Re: Dijkstra's Algorithm... With Excel! Hello ! I do appreciate tools made in plain Excel, that is without the need of macro or Visual Basic. I was interested in using an Excel sheet that empowers the Dijkstra algorithm to find out the distance betweeen two points of a given graph. That was before I discovered this topic. But still the tool I propose is built on rather different basis so it may be useful to some of you. I gave priority to concision in space (no intermediary table), nice layout (at least to my taste ), sometimes with the price of longer formulas. I included several ways to enter the information regarding the graph : direct entry in the matrix, minimal entry for unoriented graphs, entry through a table of graph links together with a distance. Rather compact, I hope this sheet can be useful !! Aldus.

 Author: RaRdEvA [ Wed Oct 26, 2016 5:12 pm ] Post subject: Re: Dijkstra's Algorithm... With Excel! aldus @ Sun Apr 29, 2012 3:52 am wrote:Hello ! ...Rather compact, I hope this sheet can be useful !!... Indeed very simple! i love it. I would like to discuss with you further, is there a chance?

 Author: Insectoid [ Wed Oct 26, 2016 6:42 pm ] Post subject: RE:Dijkstra\'s Algorithm... With Excel! Not likely, the OP hasn't posted anything in eight years.

 Author: like12 [ Mon Jan 23, 2017 3:35 am ] Post subject: RE:Dijkstra\'s Algorithm... With Excel! Wow, well done

 :