数据机构学习笔记（四） 图之单源最短路径Dijkstra算法

以下是用于实现Dijkstra算法的图：


代码实现如下：

#include<iostream>
#define MaxVertexNum 6
#define MAXNUM 65535
using namespace std;
//抽象数据类型
typedef string vertextype;//顶点类型
typedef float edgetype;//边的权值
typedef struct
{
    vertextype vex[MaxVertexNum];//顶点表
    edgetype edge[MaxVertexNum][MaxVertexNum];//邻接矩阵，也即边表
    int n;//顶点的个数
}AMGraph;
AMGraph G;
float dist[MaxVertexNum];//存放源点V0到其他各顶点的最短路径长度
int path[MaxVertexNum];//存放在源点路径上该顶点的前一个顶点的序号
//构造邻接矩阵
void create(AMGraph &G)
{
    G.n=6;
    string x[6]={"V0","V1","V2","V3","V4","V5"};
    for(int i=0;i<6;i++)
        G.vex[i]=x[i];
    int c[6][6]={{0,35,5,MAXNUM,35,MAXNUM},
                        {MAXNUM,0,MAXNUM,MAXNUM,10,MAXNUM},{MAXNUM,MAXNUM,0,10,MAXNUM,MAXNUM},
                        {MAXNUM,15,20,0,30,MAXNUM},{MAXNUM,MAXNUM,MAXNUM,MAXNUM,0,MAXNUM},
                        {MAXNUM,MAXNUM,MAXNUM,12,5,0}};
    for(int i=0;i<6;i++)
        for(int j=0;j<6;j++)
            G.edge[i][j]=c[i][j];
}
int DijkstraShortestPath(AMGraph &G,int v,float dist[],int path[])
{
    float min;
    int i,p,k;
    for(i=0;i<G.n;i++)
    {
        dist[i]=G.edge[v][i];
        if(dist[i]<MAXNUM)
            path[i]=v;
        else
            path[i]=-1;
    }
//    for(i=0;i<G.n;i++)
//        cout<<dist[i]<<" ";
//    cout<<endl;
    G.edge[v][v]=1;
    for(k=0;k<G.n-1;i++)
    {
        min=MAXNUM;
        p=-1;
        for(i=0;i<G.n;i++)
            if(G.edge[i][i]==0&&dist[i]<min)
        {
            p=i;
            min=dist[i];
        }
        if(p==-1)
        {
            cout<<"No vertex can be added in S."<<endl;
            return 0;
        }
        G.edge[p][p]=1;
        for(i=0;i<G.n;i++)
            if(G.edge[i][i]==0&&dist[i]>dist[p]+G.edge[p][i])
        {
            dist[i]=dist[p]+G.edge[p][i];
            path[i]=p;
        }
//        for(i=0;i<G.n;i++)
//            cout<<dist[i]<<" ";
//        cout<<endl;
    }
    return 1;
}
int main()
{
    int x;
    create(G);
    if(!DijkstraShortestPath(G,0,dist,path))
    {
        cout<<"path数组为："<<endl;
        for(int i=0;i<G.n;i++)
            cout<<path[i]<<" ";
        cout<<endl;
        cout<<"从V0到V1的最短路径为："<<endl;
        int t=1;
        while(dist[t]!=0)
        {
            cout<<G.vex[t]<<"<-";
            t=path[t];
        }
        cout<<G.vex[t]<<endl;
        cout<<"请输入V0到令一个点的标号："<<endl;
        cin>>x;
        cout<<"从V0到V"<<x<<"的最短路径为："<<endl;
        t=x;
         while(dist[t]!=0)
        {
            if(path[t]==-1)
            {
                cout<<"不存在路径！"<<endl;
                break;
            }
            cout<<G.vex[t]<<"<-";
            t=path[t];
        }
        cout<<G.vex[t]<<endl;
    }
    return 0;
}