DSP

对严老师的Dijkstra算法中path数组有点疑问以及个人的简化

2019-07-13 20:46发布

站内文章 / DSP
9905 0 1491
  Dijkstra算法中path保存路径上的节点 但是有行代码开始我不理解，就是       path[w] =path[v];  path[w][w] =1;    //path[w] =path[v]+[w] 开始我的理解是：  path[w] =path[v];   应该是后面代码的简写：  for (j=0;j 但是就算是上面的理解，那么对于 path[w] =path[v]+[w]  这个注释我就不理解了   下面这段代码拷贝自王道的指导全书
void ShortesPath_DIJ(MGraph G,int V0){       for (v=0;vmin+G.arc[v][w])               {dist[w] = min+G.arc[v][w];                  path[w] =path[v];  path[w][w] =1;    //path[w] =path[v]+[w]               }      }   }  
其实，对于path一维数组的实现在Mark.Allen.Weiss的数据结构与算法分析–C++.描述（第3版）就有，Mark.Allen.Weiss的Dijkstra的实现就用到了ptah[v]来保存到源点达到v定点前的一个定点，最后要得到路径，只要递归输出path就行了，下面的是c++的实现
printPath（Vextex v）{
   if(v.path !=NOT_A_VERTEX){
          printPath(v.path)  //如果c实现并且用一维数组，相应代码是 printPath(path[v]）
            count << " to ";          
 }
 count << v;
}
补充Mark.Allen.Weiss的Dijkstra算法实现的C++的数据结构
struct Vertex{
    List adj;
    bool  know;
     DistType dist;
     Vertex path;
};