一个难度高的算法问题，是数据结构上的题目，高手帮忙！！

Question

起点A到B、C、D、E四点的距离和方法依次如下：
A到B点有直接的通路，为10米
A到C点没有直接通路，(1)、从B转为：A到B为10米，B到C为50米，共60米
                    (2)、从D转为：A到D为30米，D到C为20米，共50米
A到D点有直接的通路，为30米
A到E点有直接的通路，为100米，也可以通过D转，A到D为30米，D到E为60米，共90米根据迪杰斯特拉(Dijkstra)提出的按路径长度递增的次序产生最短路径的算法，可
得到下表：
A到各点最短距离的推导过程如下：(每轮比较得到的最短可做为下轮通路)B      10(A,B)   
C      无直通        60(A,B,C)     50(A,D,C)
D      30(A,D)       30(A,D)       
E      100(A,E)      100(A,E)      90(A,D,E)       90(A,D,E)
 
最短    B              D           C                 E这样就求出了从A到各点的最短距离谁能帮我把上面的算法写成程序呢？最好能优化的，因为点可能非常多，要考虑效率

Answer 1

标号法是一种最佳算法，多用于求图的最短路问题。
    一、标号法的概念： 
     所谓标号，是指与图的每一个顶点相对应的一个数字。标号法可以说是动态规划，它采用顺推的方法，对图的每一边检测一次，没有重复的回溯搜索，因此标号法是一种最佳算法。    二、标号法的算法流程： 
     现有一图G，求从起点Vs到终点Ve的最短距离。 设：
     Sum(j)───顶点Vj的标号，代表的是Vs到Vj的最短距离。
     Vj已标味着Vs到Vj的最短路以及这条路径的长度已求出。 
     M(i,j)───Vi到Vj的非负长度。 
     H(j)───顶点Vj的前趋结点。 标号法的算法流程如下：                sum（s）←0
                   ↓
               Vs进入队列L
                   ↓      
  -----→移出队列L的队首Vk←-----
 |                 ↓                                  |
 |          Vk是不是Ve------------------|---→计算结束打印路径
 |              N∣  Y                             | 
 |                 ↓                                  |
 |           由Vk扩展出结点Vj            |
 |          （Vk与Vj之间相连）         | 
 |            Sj←Sum(k)+M(k，j)         |
 |                     ↓                              |
 |               Sj小于Sum（j）             |
 |                       |                               |
 |               Y     |    N                        |
 |                      |     --------------------
 |                      |
 |                    ↓
 |          Sum（j）←Sj
 |           H（j）← Vk
 |       Vj加入队列L并对队列L按Sum值由小到大排序
 |                    ↓
  ---------------注意：1.只有两个顶点间的距离为非负时，才可用标号法。 2.只有队列的首结点是目标结点时，才可停止计算。否则得出的不一定是最优解。三、例题解析：
     1.相邻项序列(GDOI97第四题)
    问题描述： 
     对于一个N*N(<=100)的正整数矩阵M，存在从M[A1，B1] 开始到M[A2，B2]结束的相邻项序列.两个项M[I，J]和M[K，L]相邻的件是指满足如下情况之一：
(1)I=K+-1和J=L 
     (2)I=K和J=L+-1。 
     任务：从文件中输入矩阵M，再读入K(K<=4)组M[A1，B1]和M[A2，B2]的值。对于每一组M[A1，B1]和M[A2，B2]，求一相邻项序列，使得相邻项之差的绝对值之和为最小。
     输入格式：
     4 ───N
     1 9 6 12 ───每行N个数据，共N行
     8 7 3 5 
     5 9 11 11
     7 3 2 6
     2 ───K
     4 1 1 4 ───表示A1,B1和A2,B2的值，共K行 2 2 3 4 
     输出格式：
    1 17 ───第一组数据相邻项之差的绝对值之和的最小值是17
     7 5 8 7 9 6 12───第一组数据的相邻项序列
     2 4
     7 9 11 11 
     解析：本题若将相邻的两个数看作是两个顶点，两个数之差的绝对值作为权，则问题转化成求两个顶点的最短路问题。 设：Sum[I,J]为从起点Vs到结点M[I,J]的最短距离。 H[I,J]记录结点M[I,J]的前趋结点。 L为记录待扩展的结点的队列。 鉴于数组进行排序时速度较慢，所以用链表作为记录结点的队列的类型，适于排序。
     参考程序： 
Program gdoi974;
const fang:array [1..4,1..2] of integer =((-1,0),(0,-1),(1,0),(0,1));
{上下左右四个方向}
type
{定义POINT类型,其中X,Y为结点在矩阵中的坐标,NEXT为队列中的后继结点}
    point=^note;
    note=record
         x,y:byte;
         next:point;
         end;
var
    sum:Array [1..100,1..100] of integer;
    m:Array [1..100,1..100] of integer;
    h:Array [1..100,1..100,1..2] of byte;
    f1,f2:text;
    a,b,x1,y1,x2,y2,n,k,zz:integer;
procedure print;
var
    a,b,x,y,x3,y3:integer;
    c:array [1..100] of integer;
    flag:boolean;
begin
     flag:=true; a:=1; c[a]:=m[x2,y2];
     x:=x2; y:=y2;
     while flag do
     begin
          a:=a+1; x3:=x; y3:=y;
          x:=h[x3,y3,1]; y:=h[x3,y3,2];
          c[a]:=m[x,y];
          if (x=x1) and (y=y1) then flag:=false;
     end;   {求出整条路径，放入数组C中}
     writeln (f2,zz,' ',sum[x2,y2]);
     for b:=a downto 1 do
     write (f2,c[b],' '); {打印结果}
     writeln (f2);
end;
procedure add(x,y,i:integer;var l:point);
var
   e,f,g:point;
   a,b,c:integer;
   flag:boolean;
begin
     new (e);
     e^.x:=x; e^.y:=y;
     if i=0 then l^.next:=e {加入队列}
     else begin
          f:=l; g:=f^.next; flag:=true;
          for a:=1 to i do
          begin
               if sum[g^.x,g^.y]>sum[x,y] then begin
                 e^.next:=g; f^.next:=e; flag:=false; a:=i; {加入队列}
               end;
               f:=f^.next; g:=f^.next;
          end;
          if flag then f^.next:=e; {加入队列}
          end;
end;
procedure try(xz,yz:byte);
var
   a,b,c,sj,x,y,x1,y1:integer;
   e,l,v:point;
   flag:boolean;
begin
     fillchar (sum,sizeof (sum),255); {置Sum值为-1}
     sum[xz,yz]:=0;{置起点Sum值为0}
     flag:=true;
     new (e); e^.x:=xz; e^.y:=yz;
     new (l); l^.next:=e; {起点进入队列}
     c:=1; {现在队列结点个数}
     while flag do
     begin
          v:=l^.next; dispose (l); {取出首结点V}
          l:=v; c:=c-1;{指针下移一位，结点个数减一}
          x:=v^.x; y:=v^.y;
          if (x=x2) and (y=y2) then flag:=false; {若为目标结点，则结束计算}
          if flag then
          begin
               for a:=1 to 4 do  {向四个方向扩展}
               begin
                    x1:=x+fang[a,1];
                    y1:=y+fang[a,2];
                    if (x1>0) and (x1<=n) and (y1>0) and (y1<=n) then
                    begin
                         sj:=sum[x,y]+abs (m[x,y]-m[x1,y1]);
                         if (sj < sum[x1,y1]) or (sum[x1,y1]=-1) then 
                         begin
                               sum[x1,y1]:=sj;
                               h[x1,y1,1]:=x; h[x1,y1,2]:=y;{记录路径}
                               add(x1,y1,c,l); {将新扩展出来的结点进入队列}
                               c:=c+1; {结点个数加一}
                         end;
                    end;
               end;
         end;
     end;
     print;{打印结果}
end;
Begin
     assign (f1,'gdoi974.dat');
     assign (f2,'gdoi974.out');
     reset (f1); rewrite (f2);
     readln (f1,n);
     for a:=1 to n do 
     begin
          for b:=1 to n do
             read (f1,m[a,b]);
          readln (f1);
     end; {读入数组}
     readln (f1,k);
     for a:=1 to k do
     begin
          zz:=a;
          readln (F1,x1,y1,x2,y2); {读入任务}
          try(x1,y1);
     end;
     close(f1);
     close(f2);
End.  

Answer 2

我以前自己编的,C语言的:
typedef double Graph;
double Dijkstra(Graph **G,int n,int s,int t, int *path, int *count)
{
 int i, j, *, *pathd, *pathbk;
 double w,minc,*d;
 int from, to; d=(double *)malloc(n*sizeof(double));
 =(int *)malloc(n*sizeof(int));
 pathd=(int *)malloc(n*sizeof(int));
 pathbk=(int *)malloc(n*sizeof(int));
 for (i=0; i<n; i++) [i]=0;
 for (i=0; i<n; i++) pathd[i]=0;
 for (i=0; i<n; i++)
 {
d[i]=G[s][i];
pathd[i]=s;
 }
 [s]=1; pathd[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];
  pathd[j]=w;
  }
 }
 from=s; to=t;
  for(i=0;i<n;i++)
path[i]=pathbk[i]=-1;
 j=0;
 if(d[t]!=infinity)
 {
  while(from!=to)
  {
pathbk[j]=pathd[to];
to=pathd[to];
j++;  } }  j=0;
  for(i=n-1;i>=0;i--)
if(pathbk[i]!=-1)
{
 path[j]=pathbk[i];
 j++;
}
  path[j]=t;
  *count=j+1;  return d[t];}27.  函数名：Dijkstra功能：Dijkstra算法求两点之间的最短路径用法：double _Dijkstra(Graph **G,int n,int s,int t, int *path, int *count)参数：G：邻接矩阵，n：节点数，s：开始节点，t：结束节点，path：最短路径表，count：路径数返回：最短路径程序例：#include "mylib.h" #define N 9#define m 32767 void main(){Graph a[N][N]={     m,4,m,m,m,m,m,8,m,     4,m,8,m,m,m,m,11,m,     m,8,m,7,m,4,m,m,2,     m,m,7,m,9,14,m,m,m,     m,m,m,9,m,10,m,m,m,     m,m,4,14,10,m,2,m,m,     m,m,m,m,m,2,m,1,6,     8,11,m,m,m,m,1,m,7,     m,m,2,m,m,m,6,7,m,};int *path,w,i,j,**G,count; path=(int *)malloc(N*sizeof(int));G=_Alloc2_int(N,N);for(i=0;i<N;i++) for(j=0;j<N;j++)  G[i][j]=a[i][j]; w=_Dijkstra(G,N,0,6,path,&count);printf("\n%d\n",w);for(i=0;i<count;i++){   printf("%d  ",*path);  path++;   } }
在http://www.csdn.net/develop/Read_Article.asp?Id=15180
和http://www.csdn.net/develop/Read_Article.asp?Id=15181中