我正在尝试解决 the following problem from project euler (请查看链接中的描述和示例，但这里是简短的解释)。

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

在我查看问题之后，想到的明显解决方案是从矩阵创建一个图形，然后使用 Dijkstra寻找最短路径。

为了从 N*M 矩阵构造一个图，我为每个 (i, j) 元素创建了一个顶点 i * N + j 并将其连接到任何其他顶点(可以通过 UP、RIGHT、DOWN、LEFT 连接到该顶点)，边将是我在矩阵中连接的元素的值。之后，我创建了另外 2 个顶点 -1 连接到顶点 0 和 -2 连接到 N*M - 1 这将是我的开始和结束顶点(两个连接的成本均为 0)。

在此之后，我使用 Dijkstra 来寻找从 -1 到 -2 的最短路径成本。我的 Dijkstra 实现使用优先级队列，看起来是这样的:

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
}

其中优先级队列的实现取自堆容器(例如 PriorityQueue)，并稍作修改:

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

我提供给函数的图表如下所示:

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

这可以正常工作，但问题是它被认为效率低下(根据 Hackerrank version of the problem 判断)。它应该在不到 4 秒的时间内运行并找到 700x700 矩阵的最佳解决方案的值，而我的解决方案需要 10 秒。

我认为我在 go 中做错了什么，所以我在 python 中重新实现了相同的解决方案(700x700 矩阵大约需要 70 秒)

我的问题是:我是否使用正确的方法在矩阵中找到最佳解决方案。如果是这样，我的实现有什么问题？

附言我有完整的 go 和 python 解决方案，只是认为即使没有它们问题也太长了。

最佳答案

Dijkstra应该通过了，我只是用JAVA提交，每一个任务用了不到一秒的时间就完成了。

正如我所提到的，矩阵中的每个值都可以达到 10^9，您的解决方案可能会遇到数字溢出问题，这会影响运行时间。

我的代码:

<!-- 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 );
    }
}

更新:

我认为您的 Dijkstra 实现不正确:

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,
            })
        }
    }
}

在您的实现中，您仅在顶点从堆中弹出时更新visited，因此，可以多次添加和处理一个顶点，因此，这将显着增加您的时间复杂度。

修复

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,
                })
            }
        }   
    }

关于algorithm - 找到矩阵中的最短路径总和。对于这种情况，Dijkstra 不是最优的吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30841148/