DIJ

void printfPath(int path[],int a){int stack[MAX],top=-1;while(path[a]!=-1){stack[++top]=a;a=path[a];}stack[++top]=a;while(top!=-1)cout<<stack[top--]<<" ";//出栈并打印出元素，实现了顶点的逆序打印cout<<endl;}void Dijkstra(MGraph g,int v,int dist[],int path[]){int set[MAX];int min,i,j,u;//从这句开始对数组初始化for(i =1;i<g.numEdges;i++){dist[i]=g.edegs[v][i];set[i]=0;if(g.edegs[v][i]<INF)path[i]=v;else path[i]=-1;}set[v]=1;path[v]=-1;//初始化结束for(i=1;i<=g.n;i++){min = INF; //这个循环每次从剩余顶点中选出一个顶点，通往这个顶点的//路径在通往所有剩余顶点的路径中，长度最短for(j=1;j<g.numEdges;j++)if(set[j]==0&&dist[j]<min){u=j;min=dist[j];}set[u]=1;//将选出的顶点并入最短路径中 //这个循环已刚并入的顶点作为中间点，对所有通往剩余顶点的路径进行检测for(j=1;j<=g.numEdges;j++){//这个if语句判断顶点u的加入是否会出现通往顶点j更短的路径，//如果出现，则改变原来路径及其长度，否则什么也不做 if(set[j]==0&&dist[u]+g.edegs[u][j]<dist[j]) {dist[j]=dist[u]+g.edegs[u][j];path[j]=u; }}}}