Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Dijkstra's Algorithm... With Excel!
Index -> General Programming
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Sane




PostPosted: 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. Smile

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:

Posted Image, might have been reduced in size. Click Image to view fullscreen.

Posted Image, might have been reduced in size. Click Image to view fullscreen.



Dijkstras_Algorithm_Bigger.zip
 Description:
Dijkstra's Algorithm In Excel (12 x 12 Maze)

Download
 Filename:  Dijkstras_Algorithm_Bigger.zip
 Filesize:  1.47 MB
 Downloaded:  11559 Time(s)

Sponsor
Sponsor
Sponsor
sponsor
nike52




PostPosted: Tue May 13, 2008 10:13 pm   Post subject: Re: Dijkstra's Algorithm... With Excel!

wooah that's awesome !
md




PostPosted: 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.
james3177




PostPosted: 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
andrew.




PostPosted: 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
Sane




PostPosted: Fri Aug 21, 2009 10:32 am   Post subject: Re: Dijkstra's Algorithm... With Excel!

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




PostPosted: 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
andrew.




PostPosted: Fri Aug 21, 2009 11:12 am   Post subject: RE:Dijkstra\'s Algorithm... With Excel!

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




PostPosted: 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 Wink

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
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
james3177




PostPosted: 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.
aldus




PostPosted: 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 Wink ), 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.



DijkstraAlgorithmGraphMinimalWeightedDistance120428.rar
 Description:
document .XSLX compress

Download
 Filename:  DijkstraAlgorithmGraphMinimalWeightedDistance120428.rar
 Filesize:  17.36 KB
 Downloaded:  1940 Time(s)

RaRdEvA




PostPosted: 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?
Insectoid




PostPosted: 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.
like12




PostPosted: Mon Jan 23, 2017 3:35 am   Post subject: RE:Dijkstra\'s Algorithm... With Excel!

Wow, well done
Display posts from previous:   
   Index -> General Programming
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 14 Posts ]
Jump to:   


Style:  
Search: