title: Find the shortest path sum in a matrix. Is Dijkstra not optimal for this case?
body: <p>I am trying to solve <a href="https://projecteuler.net/problem=83" rel="nofollow">the following problem from project euler</a> (please take a look at description and the example in the link, but here is the short explanation).</p>
  
  <blockquote>
    <p>in the matrix, find the  minimal path sum from the top left to the bottom right, by moving left, right, up, and down</p>
  </blockquote>
  
  <p>Right after I looked at the problem, the obvious solution which came to mind is to create a graph from the matrix and then use <a href="https://en.wikipedia.org/?title=Dijkstra%27s_algorithm" rel="nofollow">Dijkstra</a> to find the shortest path.</p>
  
  <p>To construct a graph from a <code>N*M</code> matrix, for every <code>(i, j)</code> element I create a vertex <code>i * N + j</code> and connect it to any other vertex (to which it is possible to connect with UP, RIGHT, DOWN, LEFT) and the edge will be the value of the element I am connecting to in the matrix. After that I create 2 other vertices <code>-1</code> connected to vertex <code>0</code> and <code>-2</code> connected to <code>N*M - 1</code> which will be my start and end vertices (both connection have 0 cost).</p>
  
  <p>After this I am doing Dijkstra to find shortest path cost from <code>-1</code> to <code>-2</code>. My Dijkstra implementation uses priority queue and looks this way:</p>
  
  <pre><code>func dijkstraCost(graph map[int]map[int]int, start, end int) int{
      if start == end{
          return 0
      }
      frontier := make(PriorityQueue, 1)
      frontier[0] = &amp;Item{value: start, priority: 0, index: 0}
      visited := map[int]bool{}
      heap.Init(&amp;frontier)
  
      for frontier.Len() &gt; 0 {
          element := heap.Pop(&amp;frontier).(*Item)
          vertex, cost := element.value, element.priority
          visited[vertex] = true
          neighbors := graph[vertex]
          for vertex_new, cost_new := range(neighbors){
              if !visited[vertex_new]{
                  if vertex_new == end{
                      return cost + cost_new
                  }
                  heap.Push(&amp;frontier, &amp;Item{
                      value: vertex_new,
                      priority: cost + cost_new,
                  })
              }
          }
      }
      return -1
  }
  </code></pre>
  
  <p>where Priority Queue implementation is taken from heap container (example PriorityQueue) with one minor modification:</p>
  
  <pre><code>func (pq PriorityQueue) Less(i, j int) bool {
      return pq[i].priority &gt; pq[j].priority // changed to &lt;
  }
  </code></pre>
  
  <p>The graph that I am providing to the function looks like:</p>
  
  <pre><code>map[13:map[8:965 18:121 12:746 14:111] 16:map[11:803 21:732 15:537 17:497] 3:map[8:965 2:234 4:18] 4:map[9:150 3:103] 22:map[17:497 21:732 23:37] -1:map[0:131] 17:map[16:699 18:121 12:746 22:524] 1:map[6:96 0:131 2:234] 9:map[4:18 14:111 8:965] 11:map[6:96 16:699 10:630 12:746] 19:map[14:111 24:331 18:121] 24:map[23:37 -2:0 19:956] 2:map[3:103 7:342 1:673] 15:map[10:630 20:805 16:699] 18:map[13:422 23:37 17:497 19:956] 10:map[5:201 15:537 11:803] 14:map[19:956 13:422 9:150] 0:map[5:201 1:673] 6:map[5:201 7:342 1:673 11:803] 8:map[9:150 3:103 13:422 7:342] -2:map[] 12:map[7:342 17:497 11:803 13:422] 20:map[15:537 21:732] 21:map[16:699 20:805 22:524] 5:map[0:131 10:630 6:96] 23:map[18:121 22:524 24:331] 7:map[2:234 12:746 6:96 8:965]]
  </code></pre>
  
  <hr>
  
  <p>This works correctly but the problem is that it is considered inefficient (judging by <a href="https://www.hackerrank.com/contests/projecteuler/challenges/euler083" rel="nofollow">Hackerrank version of the problem</a>). It should run find the value of the best solution for <code>700x700</code> matrix in less than 4 seconds, whereas my solution takes 10 seconds.</p>
  
  <p>I thought that I am doing something wrong in go, so I reimplemented the same solution in python (where it took approximately 70 seconds for 700x700 matrix)</p>
  
  <hr>
  
  <p><strong>My question is:</strong> Am I using the right approach to find the best solution in a matrix. If so what am I doing wrong with my implementation?</p>
  
  <p>P.S. I have full go and python solution, just thought that even without them the question is too long.</p>