C初学者求助一道课本原题（Dijkstra算法）voidShortestPathDIJ(MgraphG,intv0,PathMatrix&P,ShortPathTable&D){//求有向网G的v0顶点到其余顶点v的最短路径P[v]及其带权路径长度D[v]//若P[v][w]为TRUE,则w是从v0到v

Question

C初学者求助一道课本原题（Dijkstra算法）
void ShortestPath_DIJ(Mgraph G,int v0,PathMatrix &P,ShortPathTable &D){
//求有向网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

Answer 1

我也是初学者.不过大概看到懂：
1、D[w] = min + G.arcs[v][w];P[w] = P[v]; P[w][w] = TRUE; //P[w] = P[v] + P[w]
这句话就是传说中最短路径的“松弛”技术.（这个不懂没关系）
2、确实的,最短路径这种算法,就算你看懂了也没用,最主要是要去OJ上实践一下,才能够真正懂得算法的奥妙.
3、给你推荐几道最最简单的Dijkstra算法应用题吧：
ZOJ上的1221题；
POJ上的1258题；
ZOJ上的1406题；（这些题都是很经典的）
4、下面是我自己理解后给你写的Dijkstra算法,你的写法不好懂,我的比较清晰：
void Dijkstra()
{
int q,w;
for(q=1;q