在矩阵中找到最短路径总和。 Dijkstra是否不适用于这种情况？

Question

I am trying to solve the following problem from project euler (please take a look at description and the example in the link, but here is the short explanation).

in the matrix, find the minimal path sum from the top left to the bottom right, by moving left, right, up, and down

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 Dijkstra to find the shortest path.

To construct a graph from a N*M matrix, for every (i, j) element I create a vertex i * N + j 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 -1 connected to vertex 0 and -2 connected to N*M - 1 which will be my start and end vertices (both connection have 0 cost).

After this I am doing Dijkstra to find shortest path cost from -1 to -2. My Dijkstra implementation uses priority queue and looks this 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)

    for frontier.Len() > 0 {
        element := heap.Pop(&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(&frontier, &Item{
                    value: vertex_new,
                    priority: cost + cost_new,
                })
            }
        }
    }
    return -1
}

where Priority Queue implementation is taken from heap container (example PriorityQueue) with one minor modification:

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

The graph that I am providing to the 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 but the problem is that it is considered inefficient (judging by Hackerrank version of the problem). It should run find the value of the best solution for 700x700 matrix in less than 4 seconds, whereas my solution takes 10 seconds.

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)

---

My question is: 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.S. I have full go and python solution, just thought that even without them the question is too long.

Answer 1

Dijkstra should pass, I just make a submission using JAVA, and it took less than a second to complete each task.

As I have mentioned, each value in the matrix can go up to 10^9, your solution can encounter a number overflow problem, which can effect the 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 i = 0; i < 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 i = 0; i < 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 your Dijkstra implementation is not correct:

for frontier.Len() > 0 {
    element := heap.Pop(&frontier).(*Item)
    vertex, cost := element.value, element.priority
    //You didn't check for visited vertex here!
    visited[vertex] = true
    neighbors := graph[vertex]
    for 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 your implementation, you only update visited when the vertex pop out of the heap, thus, one vertex can be added and processed multiple time, so, it will significantly increase your 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]
        for 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,
                })
            }
        }   
    }