怎样用动态规划法求单源最短路径？

int[] cost=new int[n];//cost[i]存储i到n-1的子问题的最短路径值
int[] path=new int[n];//path[i]存储状态，使cij+cost[i]最小的j值
//对数组cost[n]和path[n]进行初始化
for(int i=0;i cost[i]=Integer.MAX_VALUE;
path[i]=-1;
}
cost[9]=0;
for(int i=n-2;i>=0;i--){
for(int j=n-1;j>=i;j--){
//得到i的邻接点
if(c[i][j](c[i][j]+cost[j])){

cost[i]=c[i][j]+cost[j];
path[i]=j;
}
}
}
System.out.println("最短路径为："+cost[0]);
int i=0;
System.out.print("0");
while(i!=n-1){
System.out.print("-->"+path[i]);
i=path[i];

话说可以用spfa或者说dijkstra。这两种主要是广度优先搜索的思想。时间复杂度分别是
O(n^2)和O(nlogn)的。这两种是比较常见的求单元最短路径。
dijkstra算法比较好写，但时间复杂度相对较高。

Procedure dijk(start:longint);
Var
b:array[-10..120] of boolean;
next:longint;
min:longint;
i,j:longint;
Begin
fillchar(b,sizeof(b),false);
d[start,start]:=0;
for i:=1 to n do begin
min:=1000000;
for j:=1 to n do begin
if (not b[j]) and (d[start,j]<>-1) and (min>d[start,j]) then
begin
min:=d[start,j];
next:=j;
end;
end;

if min<>1000000 then begin
b[next]:=true;
for j:=1 to n do
if (map[next,j]<>-1) and ( (d[start,j]>map[next,j]+d[start,next]) or (d[start,j]=-1) ) then begin
d[start,j]:=d[start,next]+map[next,j];
end;
end;
end;//for i
End;

动态规划的方法，貌似没听说过....
或许是我孤陋寡闻了...