[C++知识库]最短路径 之 迪杰斯特拉算法 C、C++

#include <cstdio>
#include <cstring>
#define Max 100
#define Maxint 1000000
typedef struct
{
    int vex,arc;
    int m[Max][Max];
}Graph;
void output(int dist[],int n)
{
    for(int i=0;i<n;i++) printf("dist[%d]=%d\n",i,dist[i]);
}
void CreatGraph(Graph &G)
{
    int i,j;
    printf("顶点 边数:");
    scanf("%d%d",&G.vex,&G.arc);
    for(i=0;i<G.vex;i++)
    {
        for(j=0;j<G.vex;j++)
        {
            if(j==i) G.m[i][j]=0;
            else G.m[i][j]=Maxint;
        }
    }
    for(i=0;i<G.arc;i++)
    {
        int e1,e2,weight;
        printf("顶点 顶点 权值:");
        scanf("%d%d%d",&e1,&e2,&weight);
        G.m[e1][e2]=weight;
        G.m[e2][e1]=G.m[e1][e2];
    }
}
int findMindist(int dist[],int s[],int n)
{
    int i;
    int flag=-1;
    int min=Maxint;;
    for(i=0;i<n;i++)
    {
        if(!s[i]&&dist[i]<min)
        {
            min=dist[i];
            flag=i;
        }
    }
    return flag;
}
void Dijkstra(Graph &G,int start)
{
    int dist[G.vex];
    int path[G.vex];
    int s[G.vex];
    int i,e=G.vex;
    for(i=0;i<e;i++)
    {
        s[i]=0;
        if(G.m[start][i]!=Maxint) path[i]=start;
        else path[i]=-1;
        dist[i]=G.m[start][i];
    }
    s[start]=1;
    int num=1;
    while(num<e)
    {
        int min=findMindist(dist,s,e);
        //printf("min=%d\n",min);
        s[min]=1;
        for(i=0;i<e;i++)
        {
            if(!s[i]&&G.m[min][i]+dist[min]<dist[i])
            {
                //printf("before:dist[%d]=%d\n",i,dist[i]);
                dist[i]=G.m[min][i]+dist[min];
                //printf("after:dist[%d]=%d\n",i,dist[i]);
                path[i]=min;
            }
        }
        num++;
    }
    output(dist,e);
}
int main()
{
    Graph G;
    CreatGraph(G);
    int start;
    printf("起点:");
    scanf("%d",&start);
    Dijkstra(G,start);
    return 0;
}