找出矩阵中的最短路径和。Dijkstra 不是最适合这种情况吗？

Question

我正在尝试从项目 euler解决以下问题（请查看链接中的描述和示例，但这里是简短的解释）。在矩阵中，通过向左、向右、向上和向下移动，找到从左上角到右下角的最小路径和在我看到问题之后，我想到的显而易见的解决方案是从矩阵创建一个图形，然后使用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}其中 Priority Queue 实现取自堆容器（示例 PriorityQueue），并进行了一个小的修改：func (pq PriorityQueue) Less(i, j int) bool {    return pq[i].priority > pq[j].priority // changed to <}这工作正常，但问题是它被认为效率低下（根据问题的Hackerrank 版本判断）。它应该700x700在不到 4 秒的时间内找到矩阵的最佳解决方案的值，而我的解决方案需要 10 秒。我认为我在 go 中做错了什么，所以我在 python 中重新实现了相同的解决方案（其中 700x700 矩阵大约需要 70 秒）我的问题是：我是否使用正确的方法在矩阵中找到最佳解决方案。如果是这样，我的实现有什么问题？PS我有完整的解决方案和python解决方案，只是认为即使没有它们，问题也太长了。