12.2迪杰斯特拉方法实现最短路径

#include<iostream>
using namespace std;
//迪杰特斯拉：邻接矩阵：一维数组+二维数组+点边数
typedef int VexType;
#define MVNum 100
#define MaxInt 32767
int S[MVNum],Path[MVNum],D[MVNum];//迪杰特斯拉的三个数组
typedef struct{
    VexType vexs[MVNum];
    int arcs[MVNum][MVNum];
    int vexnum,arcnum;
}AMGraph;
int LocateVex(AMGraph G,VexType v)
{
    for(int i=0;i<G.vexnum;++i)
        if(G.vexs[i]==v)return i;
    return -1;
}
void CreatAMGraph(AMGraph &G,int &err)
{
    cin>>G.vexnum>>G.arcnum;//输入点数边数
    for(int i=0;i<G.vexnum;++i)cin>>G.vexs[i];
    for(int i=0;i<G.vexnum;++i)
        for(int j=0;j<G.vexnum;++j)
            G.arcs[i][j]=MaxInt;     //初始化二维数组
    for(int k=0;k<G.arcnum;++k)
    {
        VexType v1,v2;
        int w;
        cin>>v1>>v2>>w;
        int i=LocateVex(G,v1),j=LocateVex(G,v2);
        if(i==-1||j==-1)    err=1;
        else    G.arcs[i][j]=w;//有向网，只用一次
    }
}
void ShortestPath_DIJ(AMGraph G,int vo)
{
    for(int v=0;v<G.vexnum;++v)//这里出的问题
    {
        S[v]=0;
        D[v]=G.arcs[vo][v];
        if(D[v]<MaxInt)Path[v]=vo;
        else Path[v]=-1;
    }
    S[vo]=1;D[vo]=0;
//     for(int i=0;i<G.vexnum;++i){
//         if(G.arcs[vo][i]!=MaxInt)//说明i与vo有边的关系
//         {
//             D[i]=G.arcs[vo][i];
//             Path[i]=vo;
//         }
//     }
    for(int k=0;k<G.vexnum-1;++k)//对剩下的n-1个顶点进行计算
    {
        int wmin=MaxInt,vmin;//找权值最小和其下标
        for(int w=0;w<G.vexnum;++w){//找权值最小的，纳入S中
            if(!S[w]&&D[w]<wmin){
                vmin=w;wmin=D[w];
            }
        }
        S[vmin]=1;
        for(int i=0;i<G.vexnum;++i){
            if(!S[i]&&(D[vmin]+G.arcs[vmin][i]<D[i]))
            {
                D[i]=D[vmin]+G.arcs[vmin][i];
                Path[i]=vmin;
            }
        }
    }
}
int main()
{
    AMGraph G;
    int err=0;
    VexType vo,ve;
    CreatAMGraph(G,err);//err的值为1的时候说明在创建邻接矩阵的时候出现了错误
    cin>>vo>>ve;
    int i=LocateVex(G,vo),j=LocateVex(G,ve);
    if(i!=-1&&j!=-1){
        ShortestPath_DIJ(G,i);
        int adj[MVNum],k=1;
        adj[0]=j;
        while(Path[j]!=i)
        {
            adj[k]=Path[j];
            j=Path[j];
            ++k;
        }
        adj[k]=i;
        for(int n=k;n>=0;--n){
            if(n!=0)cout<<G.vexs[adj[n]]<<"-->";
            else cout<<G.vexs[adj[n]];
        }
    }
    return 0;
}