Dijkstra算法是图论中的一个重要的基础算法，是解决有权图单源最短路径问题的核心算法，大家需要牢固掌握；
我们先来回顾下Dijkstra算法：WeightType dist[] 是记录最短路径值的数组，Vertex path[] 是记录最短路径下每个顶点的前驱顶点 的数组
结构体设计说明
typedef int Vertex; //顶点
typedef int WeightType; //边权
typedef int DataType; //顶点数据(点权)
//边
typedef struct _Edge{
Vertex V1,V2;
WeightType Weight;
}Edge;
//邻接矩阵存储的图
typedef struct _MGraph{
int Nv; //顶点数
int Ne; //边数
WeightType G[MaxVertexNum][MaxVertexNum]; // 邻接矩阵
DataType Data[MaxVertexNum]; //存顶点的数据 很多情况下,顶点无数据，此时不用出现
}MGraph;
Dijkstra
bool Dijkstra( MGraph* Graph,int dist[],int path[],Vertex S )
{
int collected[MaxVertexNum];
Vertex V,W;
for(V=0;VNv;V++){
dist[V] = Graph->G[S][V];
if(dist[V]Nv;W++){ //对图中的每个顶点W
if(collected[W])==false &&Graph->G[V][W]G[V][W] < 0){ //若有负边
return false; //Disjkstra算法无法解决,返回错误标记
}
if(dist[V]+Graph->G[V][W] < dist[W]){
dist[W] = dist[V] + Graph->G[V][W]; //修正dist[W]
path[W] = V; //修正S到W的路径
}
}
}
}
return true;
}
Vertex FindMinDist( MGraph* Graph,int dist[],int collected[] )
{
Vertex MinV,V;
int MinDist = INFINITY;
for(V=0;VNv;V++){
if(collected[V]==false && dist[V]
然而，很多时候会有多条最短路径
问题进阶：当有多条最短路径时，在这几条路径中挑选一条符合其他要求的路径；
此类问题往往有以下4中情况：
1.增加一个边权；即最短路径下，此边权最优的路径
2.增加一个点权；即最短路径下，经过的各个顶点点权和最优
3.直接问：有几条最短路；
4.终极问题：输出每条最短路径的具体路径；
对于前3个问题，我们往往只需增加一个对应的数组，就可以处理
案例参考：增加了一个边权 MOOC 数据结构 07-图6 旅游规划_鸿雁丨红豆灬的博客-CSDN博客
增加了点权和问最短路条数 MOOC 数据结构 1003 Emergency_鸿雁丨红豆灬的博客-CSDN博客
现在我们来重点讨论下第4种情况，要求输出每条最短路具体路径，这也是前3个问题的通用解决方法：知道了每条最短路，再根据其他权重分析每条最短路的优劣势，从而选择最优的路径；
思考：
1.要输出具体的路径，就需要保存每个顶点的每个前驱顶点，再从终点反推到起点；
2.所以需要数量等于顶点个数的数组Pre[ ]，记录每个顶点的每个前驱顶点；这些数组有的只保存一个值，即一个前驱顶点，有的保存几个；所以每个数组还需要一个值Size，来记录每个数组的元素个数；
3.用全局变量二维数组 Vertex Pre[MaxVertexNum][MaxVertexNum]，数组的第V行记录顶点V的前驱顶点；同时还需要一个全局的一维数组int Size[MaxVertexNum]，Size[V]记录顶点V的前驱顶点个数;
显然这不是一个很好的选择，最短路径下大部分顶点往往少数的前驱顶点，这就会造成极大的空间浪费；
4.那就用局部变量根据实际的顶点个数 开辟二维数组Vertex Pre[Graph->Nv][Graph->Nv]；但是传二维数组给函数时需要明确列数，好像有点麻烦，我暂时还不知道怎么传二维数组给函数；
5.那就只能把二维数组转变为一维，方便传入函数；如何将二维数组转为一维，这是我自己想的方案：那就是把数组设计进结构体，然后在局部申请一个结构体数组；可能等到后面学的更深入的时候会有更好的解决办法，到时候再分享。
结构体：
typedef struct _Path{
Vertex* Pre; //保存每个顶点的前驱顶点的数组
int Size; //每个数组的元素个数
}Path;
局部变量结构体数组
Path path[Graph->Nv];
//初始化
Vertex V;
for(V=0;VNv;V++){
path[V].Pre = malloc(Graph->Nv*sizeof(Vertex));
path[V].Size = 0;
}
6.设计好保存数据的结构，那就传入Dijkstra中，每次顶点W有更短路径前驱结点V时，if(dist[V]+Graph->G[V][W] < dist[W])，需要更新W的路径——清除前面的保存的路径，保存更短的路径V，UpdatePre( path,W,V );
void UpdatePre( Path path[],Vertex W,Vertex V )
{
path[W].Size = 0;
path[W].Pre[0] = V;
path[W].Size++;
}
当有另一条最短路时，if(dist[V]+Graph->G[V][W] == dist[W])，增加前驱结点，AddPre( path,W,V );
void AddPre( Path path[],Vertex W,Vertex V )
{
path[W].Pre[path[W].Size] = V;
path[W].Size++;
}
这样通过改良Dijkstra算法，就可以得出各个顶点的前驱顶点path[ ]
bool Dijkstra( MGraph* Graph,int dist[],Path path[],Vertex S )
{
int collected[MaxVertexNum];
Vertex V,W;
for(V=0;VNv;V++){
dist[V] = Graph->G[S][V];
if(dist[V]Nv;W++){
if(collected[W])==false &&Graph->G[V][W]G[V][W] < 0){
return false;
}
if(dist[V]+Graph->G[V][W] < dist[W]){
dist[W] = dist[V] + Graph->G[V][W];
UpdatePre( path,W,V ); //********改动点2；
}else if(dist[V]+Graph->G[V][W] == dist[W]){
AddPre( path,W,V ); //*********带动点3；
}
}
}
}
return true;
}
知道了各个顶点的前驱顶点，就可以设计递归函数，求解具体问题：当每次递归到起点时就是一条路径
终极问题：请输出每条最短路的具体路径
需要一个数组，记录每条路径的各个顶点：
Vertex SpecificShortestPath[Graph->Nv];
void DFS( Vertex Start,Vertex X,Path path[],Vertex SpecificShortestPath[],int Len );
Start 是起点，当递归到起点时，返回；
X是递归过程中的各个顶点；
path[ ]是保存每个顶点的前驱顶点的数组
SpecificShortestPath[ ] 保存具体的路径
Len 是 SpecificShortestPath[ ] 的长度
初次调用时：(Destination是终点)，Len 取 0；
DFS( Start,Destination,path,SpecificShortestPath,0 );
具体的DFS：
void DFS( Vertex Start,Vertex X,Path path[],Vertex SpecificShortestPath[],int Len )
{
SpecificShortestPath[Len] = X;
if(X==Start){
PrintShortesPath( SpecificShortestPath,Len );
return;
}
int i;
for(i=0;i
输出具体路径函数：
void PrintShortesPath( Vertex SpecificShortestPath[],int Len )
{
int i;
for(i=Len;i>=0;i--){
printf("%d ",SpecificShortestPath[i]);
}
printf("n");
}
其他问题，比如最短路的条数，考虑点权，考虑另一条边权，修改DFS都可以求解；
暂时只能想到这种程度了，等后面有更好的思路时再来讨论，诸君共勉。
