同样是层序遍历，在每次迭代中挑出最小的设置为已知
=====================================
2017年9月18日10:00:03
dijkstra并不是完全的层序遍历，在第次迭代中挑出未遍历的最小的边，一种信心的应用
=====================================
dijkstra算法是求带权单顶点到其他顶点的最短路径问题
表初始化
void InitTable(Vertex Start, Graph G, Table T) {
int i;
ReadGraph(G, T);
for (i=; i<NumVertex; i++) {
T[i].Known = False;
T[i].Dist = Infinity;
T[i].Path = NotAVertex;
}
T[Start].dist = ;
}
显示实际路径
void PrintPath(Vertex V, Table T) {
if (T[V].Path != NotAVertex) {
PrintPath(T[V].Path, T);
printf(" to");
}
printf("%v", V);
}
算法伪代码
void Dijkstar(Table) {
Vertex V, W;
for (;;) {
V = smallest unknown distance vertex;
if (V == NotAvertex)
break;
T[V].Known = True;
for each W adjacent to V
if (!T[W].Known)
if (T[V].Dist + Cvw < T[W].Dist) {
Decrease(T[W].Dist);
T[W].Path = V;
}
}
}