# How to optimize Dijkstra's algorithm for a grid graph?

I'm trying to apply Dijkstra's algorithm to the Problem 83 on projecteuler.net. The problem reads:

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297.

131   673   234   103    18
201    96   342   965   150
630   803   746   422   111
537   699   497   121   956
805   732   524    37   331


Find the minimal path sum, in matrix.txt (right click and 'Save Link/Target As...'), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by moving left, right, up, and down.

I wonder if the original algorithm can be simplified due to the fact that the graph is represented as a matrix?

In particular, I've noticed that every edge in the graph is only relaxed once (i.e. the node's distance is changed only once from infinity to some value). Can I rely on this fact in my code?

• If the degree of a graph is bounded then there are simpler and faster methods than Dijkstra's. Jan 3 '14 at 17:09

I am in love with Project Euler so that I am glad to see questions regarding it here. Be aware, however, that getting hints is somehow forbidden (note the italics :) ). The following is taken from the About page once you login:

I learned so much solving problem XXX so is it okay to publish my solution elsewhere?

It appears that you have answered your own question. There is nothing quite like that "Aha!" moment when you finally beat a problem which you have been working on for some time. It is often through the best of intentions in wishing to share our insights so that others can enjoy that moment too. Sadly, however, that will not be the case for your readers. Real learning is an active process and seeing how it is done is a long way from experiencing that epiphany of discovery. Please do not deny others what you have so richly valued yourself.

So I hope to provide a useful answer to your question while I honor the statement above ...

Regarding your first question the answer is No. There is nothing particularly interesting from the fact that you have a matrix. I see this more a matter of convenience for posting the problem than for finding the solution. I think I am not uncovering any interesting observation here since the same technique for solving this problem can be applied to arbitrary graphs.

Regarding your second question, you are right if you apply Dijkstra directly in a forward manner (ie., from the top left corner to the bottom right corner) but you have then a problem, and this is that the number of paths grows exponentially. Be sure that this problem can be solved in less than a second, ... So you should try something slightly different. Do not give up, I can see you are on the right path, so keep up pushing ...

And that's all I should say to respect the pleasure you'll get when solving this problem. Your "Aha!" moment :)

Hope this helps,

• Thank you for respecting the Project Euler etiquette about not publishing solutions and not taking away the opportunity for people to have that "aha!" moment on their own! I admire and appreciate your integrity.
– D.W.
Jan 3 '14 at 1:21
• Ouch mate, ... thanks really, thanks a lot for your comment! I really found that moving! I do really appreciate that (as much as your work in stackexchange :) ) As I said I am in love with projecteuler :) Jan 3 '14 at 1:26
• I don't need a solution as I've already solved the problem. I wonder how Dijkstra can be simplified when working with a matrix. Thank you, but this doesn't answer the question.
– user12525
Jan 3 '14 at 12:35
• Actually, presenting as a matrix makes an enormous difference! It means we're looking for a least-weight path in a square grid graph, rather than a general graph. (OK, it's not the matrix per se, since the information could be presented in any convenient way but the concommitant restriction on the input is huge.) Jan 3 '14 at 18:23
• @David Richerby: you are definitely right in both regards. My answer was not very accurate indeed and all I meant is what you note between parenthesis. In fact, while the problem makes sense on every graph (as I already noted) the impact of the solution is clearer in grids. Good point David Jan 3 '14 at 18:36