c - 二元矩阵两点之间的最短路径

Question

我想找到二进制矩阵的两点之间的最短路径。

矩阵的来源和目的地由用户给出。我们只能选择矩阵中为 1 的位置，并且还可以沿对角线、左、右、上和下移动。

如果移动是对角线，则成本为根 2，否则为 1。所以我想要一个如何找到它的算法。

Answer 1

您正在寻找的是单源最短路径算法，这意味着您在图中选择一个源节点（例如）并找到所有或一个节点的最短路径。为此目的存在几种算法 -

• Dijkstra 算法

• 贝尔曼福特算法

• 一种星搜索算法

• Floyd Warshall 算法

• 约翰逊算法

我的建议是您阅读这些内容并选择适合您目的的内容。