关于Dijkstra算法的一些困惑?

Question

问题在注释中已标明
void Dijkstra(graph &G,int v,float dist[],int prev[])
{ int i, j, u; float min; int *S=new int [G.count];
for(i=0; i<G.count; i++)
{
dist[i]=G.adjmat[v][i]; prev[i]=v; S[i]=0;
}
S[v]=1;
prev[v]=-1;
for(i=1; i<G.count; i++) //为什么要添加这一层循环？
{
min=INF;
for(j=0; j<G.count; j++)
if(!S[j] && dist[j]<min)
{
min=dist[j]; u=j;
}
if(min==INF) break;
S[u]=1;
for(j=0; j<G.count; j++)
if(!S[j] && dist[j]>dist[u]+G.adjmat[u][j])
{
dist[j]=dist[u]+G.adjmat[u][j]; prev[j]=u;
}
}
}

Answer 1

Dijkstra算法是一个动态规划算法，这里的转移方程你的代码中已经写出来了
dist[j]=dist[u]+G.adjmat[u][j];
也就是说指定顶点k到j的最短距离＝对于任意前序节点u，k到u的最短距离dist[u]＋uj之间的边长，
如果去掉你注释的那一行，这里面的u达不到对任意的前序节点这个条件，
因为根据代码，当j还没有遍历到比j大的顶点x时，dist[x]还没有被计算，
如果只有一层循环
for(j=0; j<G.count; j++)
if(!S[j] && dist[j]>dist[u]+G.adjmat[u][j])
{
dist[j]=dist[u]+G.adjmat[u][j]; prev[j]=u;
}
这段代码中的u只可能在比j小的前序节点中进行搜索，
所以二层循环保证了，上面这段代码的子结构是全局的