找出矩阵中的最短路径和。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解决方案，只是认为即使没有它们，问题也太长了。