Dijkstra's Algorithm... With Excel!

[Sane]

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:

[nike52]

wooah that's awesome !

[md]

you clearly have WAY too much time on your hands... but awesome none the less.

[james3177]

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

[andrew.]

It's truly amazing what you can do with Excel. Good job man.

+Bits

[Sane]

james3177 @ Thu Aug 20, 2009 5:11 pm wrote:

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

It's tricky to change the grid size. If I remember correctly... the outer loop takes N iterations, where N is the number of vertexes. So if you want a grid that is 14x14, you need to change all of the tables to have 196 rows and 196 columns. Then you will have to change all of the ranges accordingly, and fill in the remaining rows and columns.

There's a 6x6 example that I posted if you want to compare: http://www.programmingforums.org/post145190.html

By the way, I am freaking out a lot right now... Yesterday I was lying on my bed at 7 p.m. trying to think up a contest problem and had a totally random flashback to the time I made this Excel program. I came online right away to send it to a friend because I thought he would find it interesting. He can verify this. Then only 15 minutes ago I checked my inbox to find an e-mail message at 11:00 AM from you giving me bits to help you out. I came here thinking that my friend must have told a friend who told you. But I see your post was made yesterday at 5 p.m (6 p.m. my time). BEFORE I had told my friend. I posted this a year ago... and hadn't thought about it or even came to compsci.ca for a moment since then... and then this happens 1 hour apart. WTF is this... Please tell me you're actually my friend and you hacked the forum timestamp to mess with me...

[saltpro15]

"There are no coincidences, only the illusion of coincidence" - V for Vendetta


really cool btw Sane

[andrew.]

Just a weird coincidence (if you believe in coincidences).

[Tony]

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

[james3177]

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.

[aldus]

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.

[RaRdEvA]

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?

[Insectoid]

Not likely, the OP hasn't posted anything in eight years.

[like12]

Wow, well done