基于Dijkstra算法的最短路径问题求解

进行类的设计与实现，解决最短路径问题。具体要求如下：
（1） 采用图的邻接矩阵或邻接表实现最短路径问题中图的存储；
（2） 采用Dijkstra算法求从某个源点到其余各顶点的最短路径；
（3） 将上述功能作为类的成员函数实现，编写主函数测试上述功能。

这个在严蔚敏的数据结构书的差不多都有源码了吧。
void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D)
{ // 算法7.15
  // 用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]
  // 及其带权长度D[v]。
  // 若P[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点。
  // final[v]为TRUE当且仅当v∈S,即已经求得从v0到v的最短路径。
  int i=0,j, v,w,min;
  bool final[MAX_VERTEX_NUM];
  for (v=0; v<G.vexnum; ++v) {
  final[v] = FALSE;  
  D[v] = G.arcs[v0][v].adj;
  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顶点属于S集
  //--- 开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集 ---
  for (i=1; i<G.vexnum; ++i) { // 其余G.vexnum-1个顶点
  min = INFINITY; // 当前所知离v0顶点的最近距离
  for (w=0; w<G.vexnum; ++w)
  if (!final[w]) // w顶点在V-S中
  if (D[w]<min) { v = w; min = D[w]; } // w顶点离v0顶点更近
  final[v] = TRUE; // 离v0顶点最近的v加入S集
  for (w=0; w<G.vexnum; ++w) // 更新当前最短路径及距离
  if (!final[w] && (min+G.arcs[v][w].adj<D[w])) { 
  // 修改D[w]和P[w], w∈V-S
  D[w] = min + G.arcs[v][w].adj;
  for(j=0;j<G.vexnum;j++) P[w][j] = P[v][j]; //第v行赋值于第w行
  P[w][w] = TRUE; // P[w] = P[v]+[w]
  }//if
  }//for
} // ShortestPath_DIJ
加个主函数就可以测试了。