1.综述
 
 　　Dijkstra算法解决的是带权重的有向图上单源最短路径问题，该算法要求所有边的权重都为非负值。
 
 　　算法重复从结点集 V-S中选择最短路径估计最小的结点 u ,将 u 加入到集合 S ,然后对所有从 u 出发的边进行
 
 　　松弛操作（相当于遍历选出最小权值）。使用一个最小优先队列 Q 来保存结点集合。（代码实现中：设置一个标记数组）。迪科斯彻算法使用了广度优先搜索算法。算法解决的是有向图中单个源点到其他顶点的最短路径问题。sat答案
 
 　　迪克斯拉算法类似于广度优先算法，也类似于计算最小生成树的 Prim 算法。
 
 　　2.代码
 
 　　int Dijkstra（Graph G,int n,int s,int t, int path[]）
 
 　　{
 
 　　int i,j,w,minc,d[max_vertexes],mark[max_vertexes];
 
 　　for （i=0;i<n;i++） mark[i]=0;
 
 　　for （i=0;i<n;i++）
 
 　　{ d[i]=G[s][i];
 
 　　path[i]=s; }
 
 　　mark[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 （（mark[j]==0）&&（minc>=d[j]）） {minc=d[j];w=j;}
 
 　　mark[w]=1;
 
 　　for （j=0;j<n;j++）
 
 　　if （（mark[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];
 
 　　}
 
 　　3.理解
 
 　　代码中参数：
 
 　　G:
 
 　　图，用邻接矩阵表示
 
 　　n:
 
 　　图的顶点个数
 
 　　s:
 
 　　开始节点
 
 　　t:
 
 　　目标节点
 
 　　path[]:
 
 　　用于返回由开始节点到目标节点的路径
 
 　　返回值：
 
 　　最短路径长度
 
 　　注意：
 
 　　输入的图的权必须非负
 
 　　顶点标号从0开始
 
 　　用如下方法打印路径：
 
 　　i=t;
 
 　　while （i!=s）
 
 　　{
 
 　　printf（"%d<--",i+1）；
 
 　　i=path[i];
 
 　　}
 
 　　printf（"%d\n",s+1）；
 
 　　1.初始化：先初始化源点 s 的 d[]数组的值，即把与源点相连的点的权值赋给 d[] 数组。
 
 　　2.用了三个 for 循环，一个 for 循环里面镶嵌两个并列的 for 循环。第一个 for 循环和第二个 for 循环是找出当前要进行松弛的结点，第三个 for 循环进行松弛操作。
 
 　　3.第三个 for 循环中的
 
 　　[cpp] view plaincopy在CODE上查看代码片派生到我的代码片
 
 　　d[j]>d[w]+G[w][j]
 
 　　其中 d[j] 也包括 d[j] 取值为无穷大的情况，其真实性意义就是 j 点与源点不相连，直接把 d[j] 赋值为当前进行松弛的点 w 加上 w 到 j 点的权值。托福答案