algorithm - Find the shortest path sum in a matrix. Is Dijkstra not optimal for this case? -

i trying solve the following problem project euler (please take @ description , example in link, here short explanation).

in matrix, find minimal path sum top left bottom right, moving left, right, up, , down

right after looked @ problem, obvious solution came mind create graph matrix , use dijkstra find shortest path.

to construct graph n*m matrix, every (i, j) element create vertex i * n + j , connect other vertex (to possible connect up, right, down, left) , edge value of element connecting in matrix. after create 2 other vertices -1 connected vertex 0 , -2 connected n*m - 1 start , end vertices (both connection have 0 cost).

after doing dijkstra find shortest path cost -1 -2. dijkstra implementation uses priority queue , looks way:

func dijkstracost(graph map[int]map[int]int, start, end int) int{     if start == end{         return 0     }     frontier := make(priorityqueue, 1)     frontier[0] = &item{value: start, priority: 0, index: 0}     visited := map[int]bool{}     heap.init(&frontier)      frontier.len() > 0 {         element := heap.pop(&frontier).(*item)         vertex, cost := element.value, element.priority         visited[vertex] = true         neighbors := graph[vertex]         vertex_new, cost_new := range(neighbors){             if !visited[vertex_new]{                 if vertex_new == end{                     return cost + cost_new                 }                 heap.push(&frontier, &item{                     value: vertex_new,                     priority: cost + cost_new,                 })             }         }     }     return -1 } 

where priority queue implementation taken heap container (example priorityqueue) 1 minor modification:

func (pq priorityqueue) less(i, j int) bool {     return pq[i].priority > pq[j].priority // changed < } 

the graph providing function looks like:

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]] 

---

this works correctly problem is considered inefficient (judging hackerrank version of problem). should run find value of best solution 700x700 matrix in less 4 seconds, whereas solution takes 10 seconds.

i thought doing wrong in go, reimplemented same solution in python (where took approximately 70 seconds 700x700 matrix)

---

my question is: using right approach find best solution in matrix. if doing wrong implementation?

p.s. have full go , python solution, thought without them question long.

dijkstra should pass, make submission using java, , took less second complete each task.

as have mentioned, each value in matrix can go 10^9, solution can encounter number overflow problem, can effect running time.

my code:

<!-- language:java -->  static int[]x = {0,1,0,-1}; static int[]y = {1,0,-1,0}; public static void main(string[] args) throws filenotfoundexception {     // printwriter out = new printwriter(new fileoutputstream(new file(     // "output.txt")));     printwriter out = new printwriter(system.out);     scanner in = new scanner();             int n = in.nextint();     long[][]map = new long[n][n];     for(int = 0; < n; i++){         for(int j = 0; j < n; j++){             map[i][j] = in.nextlong();         }     }     priorityqueue<pos> q= new priorityqueue();     long[][]dist = new long[n][n];     for(long[]a : dist){         arrays.fill(a,long.max_value);     }     q.add(new pos(0,0,map[0][0]));     dist[0][0] = map[0][0];     while(!q.isempty()){         pos p = q.poll();         if(dist[p.x][p.y] == p.cost){             for(int = 0; < 4; i++){                 int x = p.x + x[i];                 int y = p.y + y[i];                 if(x >= 0 && y >= 0 && x < n && y < n && dist[x][y] > dist[p.x][p.y] + map[x][y] ){                     dist[x][y] = dist[p.x][p.y] + map[x][y];                     q.add(new pos(x,y,dist[x][y]));                 }             }         }     }     out.println(dist[n - 1][n - 1]);     out.close(); }  static class pos implements comparable<pos>{     int x, y;     long cost;     public pos(int x, int y, long cost) {         super();         this.x = x;         this.y = y;         this.cost = cost;     }     @override     public int compareto(pos o) {         // todo auto-generated method stub         return long.compare(cost, o.cost );     } } 

update:

i think dijkstra implementation not correct:

for frontier.len() > 0 {     element := heap.pop(&frontier).(*item)     vertex, cost := element.value, element.priority     //you didn't check visited vertex here!     visited[vertex] = true     neighbors := graph[vertex]     vertex_new, cost_new := range(neighbors){         if !visited[vertex_new]{//you can add same vertex multiple times here!             if vertex_new == end{                 return cost + cost_new             }             heap.push(&frontier, &item{                 value: vertex_new,                 priority: cost + cost_new,             })         }     } } 

in implementation, update visited when vertex pop out of heap, thus, 1 vertex can added , processed multiple time, so, increase time complexity.

to fix

for frontier.len() > 0 {     element := heap.pop(&frontier).(*item)     vertex, cost := element.value, element.priority     if !visited[vertex]{         visited[vertex] = true         neighbors := graph[vertex]         vertex_new, cost_new := range(neighbors){             if !visited[vertex_new]{                 if vertex_new == end{                    return cost + cost_new                 }                 heap.push(&frontier, &item{                    value: vertex_new,                    priority: cost + cost_new,                 })             }         }        }