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?
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,