Dijkstra算法解决的是带权重的有向图上单源最短路径问题，该算法要求所有边的权重都为非负值。
算法重复从结点集 V-S中选择最短路径估计最小的结点 u ，将 u 加入到集合 S ，然后对所有从 u 出发的边进行
松弛操作（相当于遍历选出最小权值）。使用一个最小优先队列 Q 来保存结点集合。（代码实现中：设置一个标记数组）。迪科斯彻算法使用了广度优先搜索算法。算法解决的是有向图中单个源点到其他顶点的最短路径问题。
迪克斯拉算法类似于广度优先算法，也类似于计算最小生成树的 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=d[j])) {minc=d[j];w=j;}
mark[w]=1;
for (j=0;jd[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 点的权值。
想要理解 Dijkstra 算法的最简便路径就是把上面的模板背下来好好理解，背诵是理解的最短路径。昨天晚上在
图书馆写了一遍 Dijkstra 算法，外加看算法导论理解，从图书馆到宿舍的路上一直在理解 Dijkstra 算法，原来想通一个算法是多么幸福的事。