请大家帮忙做一道题！！十分着急！！

Question

为了大家看着方便，我顺便翻译一下^-^此题翻译过来(再加以简化)是这样的： 已知：一个二维数组有M行N列。 
求解：一条路经 
条件：1.它是由数组内各个连续的单元连接而成，所谓连续是指两个单元在同一行或同一列,且中间没有其他单元(说白了就是两个单元挨着:P) 
2.这条路径内各单元数值之和是包含在全部单元中的。(这句话我估计翻译的不太对，把原句也贴上，可以讨论一下,原句是The cost of a path is the summary of all the cells´ costs involved.) ★请做出一条各个单元内数值相加之和最小的路径★ 要求：1.描述此模块用到了哪些API 
2.画出UML图(这个我想应该是流程图吧) 
3.用java或者C++写出此模块 
4.写出你的解题思路 题目给定函数如下(共三部分Map,Cell和Trace)： 
(Map) 
M: int 
N: int 
getCell(int row, int col): Cell 
getStartCell(): Cell 
getTargetCell(): Cell 
解释如下： 
M: 行数 
N: 列数 
getCell 返回指定单元的行列数.index从0开始 
getStartCell和GetTargetCell返回开始的单元和结束的单元 (Cell) 
row: int 
col: int 
getCost(): int (Trace) 
getTraceLength(): int 
getCell(int n): Cell 
getCost(): int 
解释如下： 
getTraceLength返回这条路径一共包括多少个单元 
getCell返回这条路径所经过的第n个单元 
getCost返回这条路径中所有单元中数值的和 

Answer 1

可以把这个数组理解成一个加权（每个Cell的Cost）的图，把这个问题转化为一个在图中求最小路径的问题。
算法里面有一个好像迪杰特斯拉算法专门解决这种问题的，在数据结构图的一章找找看。做起来太麻烦了，自己努力一下吧。（要不是在加班还可能试试：）

Answer 2

狄克斯特拉（Dijkstra）算法和思路我都明白，问题是我代码写不出来，555 ~~~>_<~~~~大家帮忙。

Answer 3

关于最短路径算法的资料我提供给大家，希望大家能给出代码(java\c++\c#都可以)资料如下：
http://ress.wtusm.edu.cn/garden/courseware/gis/ch5/5.7.2.htm#最短路径分析

Answer 4

求最短路径，首先要有一个二维矩阵，然后得到这个二维矩阵的邻接矩阵，然后就可以用Dijkstra算法了(当然，你还要注意矩阵是否有权值等).具体的可到数据结构/算法版去问//G:邻接矩阵，n:节点个数 s:起点 t:终点
    public int Dijkstra(int[][] G,int n,int s,int t,int path[])
    {
        int i,j,w,minc, d[], [];
        d = new int[n];
         = new int[n];
        for (i=0; i<n; i++) [i]=0;        for (i=0; i<n; i++)
        {
            d[i]=G[s][i];
            path[i]=s;
        }        [s]=1;
        path[s]=0;
        d[s]=0;        for(i=1; i<n; i++)
        {
            minc = infinity;
            w = 0;
            for( j = 0; j < n; j++ )
              if( ( [j]==0 ) && ( minc >= d[j] ) )
              {
                minc=d[j];w=j;
              }
            [w]=1;
            for(j=0; j<n; j++)
              if( ([j]==0) && ( G[w][j] != infinity ) && ( d[j] > d[w]+G[w][j] ) )
                {
                   d[j]=d[w]+G[w][j];
                   path[j]=w;
                }
       }
       return d[t];
    }path里面存放的是最短路径.
一般情况下,应该是这样使用得到的path数组的:
假设源点是1.目标点是3.共有6个点.
则path有6个元素,从path[1]到path[6].
取path[3].得到4,则说明要从1走到4再走到3,最短
那么,从1走到4又怎么走最短呢?就是取path[4]了.
这是一个递归的过程.

Answer 5

我以前用C编过
没用递归，用FOR嵌套