哪位高手能帮小弟我矩阵的一个点到另一个点的最短距离！多谢

谁能帮我求一个矩阵的一个点到另一个点的最短距离！谢谢！
如下面
3*3的矩阵
1  30 45
21 3  18
32 2  32
请问怎么才能求出点（0,0）到点（2，2）的最短距离
希望能给出代码

------解决方案--------------------
我提供一个简单的思路：
例如(a,b) 到点 (c,d).
可以证明，走过的路不能回头，那么的话就必须经过c-a步的横向的移动，以及d-b步纵向的移动才能到达目的坐标。
横向的移动和纵向的移动的相对顺序是不能确定的。可以看成是（c-a）+ (d-b)个元素的全排列。
这样就抽象成了这明显可以回溯法来进行解决。
在查找过程中，可以利用约束和限界函数来缩小搜索范围。例如记录已搜索路径的最小值，若当前路径的值大于最小值，那么该路径就不用搜索了。
------解决方案--------------------
相邻的点之间连一条边。。转化为一个图。。然后用Dijkstra算法求最短路。。
------解决方案--------------------
请看数据结构书 Dijkstra算法
------解决方案--------------------

引用:

Quote: 引用:

相邻的点之间连一条边。。转化为一个图。。然后用Dijkstra算法求最短路。。

好像很难转换为图吧
那转换为图后，怎么才能记录经过的点

建图有什么难的。。不就相邻的点连边。。好像(0,0)和(0,1),(1,0)两个点各连一条双向边。。记录经过的点你在Dijkstra松弛操作的时候记录就行了。。如果不清楚这个算法。。建议你看看数据结构的书。。
------解决方案--------------------

引用:

Quote: 引用:

Quote: 引用:

Quote: 引用:

相邻的点之间连一条边。。转化为一个图。。然后用Dijkstra算法求最短路。。

好像很难转换为图吧
那转换为图后，怎么才能记录经过的点

建图有什么难的。。不就相邻的点连边。。好像(0,0)和(0,1),(1,0)两个点各连一条双向边。。记录经过的点你在Dijkstra松弛操作的时候记录就行了。。如果不清楚这个算法。。建议你看看数据结构的书。。

如果建图怎么才能求点自身的距离呢？

什么叫点自身的距离。。点到自己的距离肯定是0啊。。。
------解决方案--------------------

引用:

Quote: 引用:

Quote: 引用:

Quote: 引用:

Quote: 引用:

Quote: 引用:

相邻的点之间连一条边。。转化为一个图。。然后用Dijkstra算法求最短路。。

好像很难转换为图吧
那转换为图后，怎么才能记录经过的点

建图有什么难的。。不就相邻的点连边。。好像(0,0)和(0,1),(1,0)两个点各连一条双向边。。记录经过的点你在Dijkstra松弛操作的时候记录就行了。。如果不清楚这个算法。。建议你看看数据结构的书。。

如果建图怎么才能求点自身的距离呢？

什么叫点自身的距离。。点到自己的距离肯定是0啊。。。

可是你看这
3*3的矩阵
1  30 45
21 3  18
32 2  32
他的每个点都有值的
应该不能把他忽略吧。
比如要求怎么才能求呢

你可以求出最短路径之后。。再加上起点自身的权值的。。
------解决方案--------------------
3X3，把所有路径走一遍就可以了

00-01-02-12-22 ，列出所有可能的组合，重复也没关系

哪位高手能帮小弟我矩阵的一个点到另一个点的最短距离！多谢

相关推荐