Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
Dijkstra's Algorithm... With Excel!
Author Message
Sane

Posted: 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:

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

Filename:  Dijkstras_Algorithm_Bigger.zip
Filesize:  1.47 MB

nike52

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

wooah that's awesome !
md

Posted: 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

Posted: 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?

andrew.

Posted: 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

Posted: 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?

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

Posted: 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.

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

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

Tony

Posted: 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
Tony's programming blog. DWITE - a programming contest.
james3177

Posted: 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

Posted: 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.

DijkstraAlgorithmGraphMinimalWeightedDistance120428.rar
Description:
 document .XSLX compress

Filename:  DijkstraAlgorithmGraphMinimalWeightedDistance120428.rar
Filesize:  17.36 KB

RaRdEvA

Posted: 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

Posted: 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

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

Wow, well done
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 14 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: