void shortestpath_dij(mgraph G,int v0,pathmatrix &p,shortpathtable &d)
{
//用dijkstra算法求有向图G的v0顶点到其余v的最短路径p[v]及其带权长度D[V]
//若p[v][w]为true,那么w是从v0到v当前求得最短路径上的点
//final[v]为true当且仅当v属于s，即已经求得从v0到v的最短路径
for(v=0;v<G.vexnum;v++)
{
final[v]=false;
d[v]=G.arcs[v0][v];
for(w=0;w<G.vexnum;w++)
p[v][w]=false; //设置空路径
if(d[v]<infinity)
{p[v][v0]=true;p[v][v]=true;} //???不明白
}
d[v0]=0;final[v0]=true;
//开始主循环，每次求得v0到某个v定点的最短路径，并且加v入到s集
for(i=1;i<G.vexnum;i++)
{
min=infinity; //infinity是无穷的大数
for(w=0;w<G.vexnum;w++)
if(!final[w])
if(d[w]<min) {v=w;min=d[w];}
final[v]=true;
for(w=0;w<G.vexnum;w++) //更新当前最短路径和距离 ??不明白
if(!final[w] && (min+G.arcs[v][w])<d[w])
{d[w]=min+G.arcs[v][w];
p[w]=p[v];
p[w][w]=true;
}
}
}
提问：
1.if(d[v]<infinity)
{p[v][v0]=true;p[v][v]=true;} // 为什么还要p[v][v0]=true呢?
2.for(w=0;w<G.vexnum;w++) //更新当前最短路径和距离
if(!final[w] && (min+G.arcs[v][w])<d[w])
{d[w]=min+G.arcs[v][w];
p[w]=p[v];
p[w][w]=true;
}
更新d[w]中的数据有什么用处呢?
