评析dijsktra算法

dijsktra算法的最大优点是：用矩阵来存储走过的顶点，这一点足够自己学习了。
还有就是，它非常彻底的贯彻了用空间换时间的思想，实际上，空间换时间，还可以简化编码的复杂度，提高程序的易读性。

还有一些程序的计算技巧，这一点就先不述了，先搞定大数相乘吧！
源代码如下：

#include <cstdio> #include <cstdlib> //using namespace std; #define SIZE 6 #define INFINITY 0X7FFFFFFF int arcs[SIZE][SIZE]={0,INFINITY,10,INFINITY,30,100,\                      INFINITY,0,5,INFINITY,INFINITY,INFINITY,\                      INFINITY,INFINITY,0,50,INFINITY,INFINITY,\                      INFINITY,INFINITY,INFINITY,0,60,10,\                      INFINITY,INFINITY,INFINITY,20,0,60,\                      INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,0}; bool flag[SIZE]={false,false,false,false,false,false}; int Dis[SIZE]={0,0,0,0,0,0};//保存v0到其他各点的距离 bool ArcTop[SIZE][SIZE]; void Init() {//初始化矩阵         for(int i=0;i<SIZE;i++)         {             Dis[i]=arcs[0][i];                for(int j=0;j<SIZE;j++)             {                     ArcTop[i][j]=false;             }             if(Dis[i]<INFINITY)             {      ArcTop[i][0]=true;      ArcTop[i][i]=true;             }         }          } void ShortestPath_DIJ() {      //第一个节点      Dis[0]=0;      flag[0]=true;      for(int i=1;i<SIZE;i++)      {              int min=INFINITY;              int temp;//              //下面这个for循环查找Dis[]不断更新min的值              for(int j=0;j<SIZE;j++)              {                  if(!flag[j])                  {                      if(Dis[j]<min)                      {                        temp=j;                        min=Dis[j];                       }                  }              }              flag[temp]=true;//              for(int kk=0;kk<SIZE;kk++)              {                                  if(!flag[kk]&&arcs[temp][kk]!=INFINITY&&min+arcs[temp][kk]<Dis[kk])                         {//只要temp结点为源，如果能更新，都更新。                           Dis[kk]=min+arcs[temp][kk];                           for(int k=0;k<SIZE;k++)                           {                           ArcTop[kk][k]=ArcTop[temp][k];//所经过的结点保存起来，经过一次，把结点保存一次                           }                           ArcTop[kk][kk]=true;                                                                          }              }                       }          } void Output() {      for(int i=0;i<SIZE;i++)      {          for(int j=0;j<SIZE;j++)          {                  if(ArcTop[i][j])                  printf("%d",j);          }          printf("\n");      } }      int main() { Init(); ShortestPath_DIJ(); Output(); system("PAUSE"); return 0; }