仔细分析Dijkstra算法的执行过程可以发现,它与洪水泛滥有些类似。把图节点想象成洪水将要经过的城镇,所有边想象连接城镇的河道,假定洪水在源点突然爆发。
       在时刻0,洪水从源头A城开始泛滥。洪水检测员可以估计洪水到达B城、C城、G城、D城的时刻分别为第i、j、k、t小时,i有限小而j,k,t为无穷大因为他们绝不与A城相邻,而B却与之相邻。前者是最保守的估计--- 情况不可能更糟了。若洪水监测员的职责仅仅是正确预报各个城市最早被淹的时间,则他大可高枕无忧睡上 min{i,j,k,t}=i 小时。当洪水到达B时,监测员着手检查所有与B相邻的有河道相邻又尚未被淹的城市,假定发现洪流从B推进到C、D、G的时间分别为12、5、7小时,于是他将C、D、G被淹时刻提前到12+j,5+k,7+t。而这个将时刻提前的动作就是Dijkstra算法里的降距操作。

int Dijkstra(int n,int s,int t, int path[])   // s为源,t为目标终点,path[n]用于跟踪各节点到源的最短路径
{
   
int i,j,w,minc,d[N],mark[N];
  
   memset(mark,
0,sizeof(mark));
   
for (i=0;i<n;i++)
    
{
       d[i]
=g[s][i];    // 初始化点i到源的最短路,有弧赋权,无弧的置为正无穷
       path[i]=s;
    }

   mark[s]
=1;
   path[s]
=-1;
   d[s]
=0;
   
for (i=1;i<n;i++)
     
{
        minc
=maxint;
        
for (j=0;j<n;j++)
        
{
          
if ((mark[j]==0)&&(minc>=d[j]))  // 若点j未被求解,且距源的长度有穷
          {minc=d[j];w=j;}
        }

          
        mark[w]
=1;    // 归并该点
        for (j=0;j<n;j++)
        
if (mark[j]==0&&d[j]>d[w]+g[w][j])
           
{
             d[j]
=d[w]+g[w][j];
            
             path[j]
=w;
           }

     }

     
return d[t];
}