最短路径Dijkstra算法

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MaxSize 20
#define INFINITY 666

typedef char VertexType;

//定义图 的邻接矩阵表示法结构
typedef struct Graph {
    VertexType ver[MaxSize+1];// 顶点表，是一位数组
    int edg[MaxSize][MaxSize];// 邻接矩阵，可以看做是边表
}Graph;

//邻接矩阵法图的生成函数
void CreateGraph( Graph *g ){
    int i = 0;
    int j = 0;
    int VertexNum;
    VertexType Ver;
    while( ‘\n‘ != (Ver=getchar()) )
        g->ver[i++] = Ver;
    g->ver[i] = ‘\0‘;
    VertexNum = strlen(g->ver);
    for( i=0; i<VertexNum; i++ )
        for( j=0; j<VertexNum; j++ )
            scanf("%d", &g->edg[i][j]);

}

//求图的顶点数
int CalVerNum( Graph g ){
    return strlen(g.ver);
}

//将不邻接的顶点之间的权值设置为INFINITY
void SetWeight( Graph *g ){
    int i, j;
    for( i=0; i<CalVerNum(*g); i++ ){
        for( j=0; j<CalVerNum(*g); j++ ){
            if( -1 == g->edg[i][j] )
                g->edg[i][j] = INFINITY;
        }
    }
}


//Dijkstra求最短路径函数
void Dijkstra( Graph g ){
    int VertexNum = CalVerNum( g );
    int i, j, k, m, n;
    int mini;
    int *used = (int *)malloc(sizeof(int)*VertexNum);
    int *distance = (int *)malloc(sizeof(int)*VertexNum);
    int *parent = (int *)malloc(sizeof(int)*VertexNum);
    SetWeight( &g ); //设置权值
    printf("读取到的顶点依次为：");
    for( i=0; i<VertexNum; i++ ){
        printf(" %c  ",g.ver[i]);
    }
    printf("\n\n");
    
    printf("读取到的邻接矩阵为(666表示无穷大)\n");
    for( i=0; i<VertexNum; i++ ){
        for( j=0; j<VertexNum; j++ ){
            printf("%d  ",g.edg[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    printf("请输入起点和终点(空格隔开)：");
    char a,b;
    int st,en;
    fflush(stdin);
    scanf("%c %c",&a,&b);
    for( i=0; i<VertexNum; i++ ){
        if(g.ver[i] == a){
            st = i;
        }
        if(g.ver[i] == b){
            en = i;
        }
    }
    for( i=0; i<VertexNum; i++ ){
        used[i] = 0;
        parent[i] = 0;
        distance[i] = g.edg[st][i];//初始化为与编号为0的顶点的距离
    }
    used[st] = 1;
    for( i=0; i<VertexNum-1; i++ ){
        j = 0;
        mini = INFINITY;
        for( m=0; m<VertexNum; m++ ){
            if((0 == used[m]) && (distance[m] < mini) ) {
                mini = distance[m];
                j = m; //j为刚刚找到的V-U中到源点路径最短的顶点
            }
        }
        used[j] = 1;
        for( n=0; n<VertexNum; n++ ){
            if( (0 == used[n]) && (distance[n] > distance[j] + g.edg[j][n]) ){//由于有顶点新加入U集合，对距离数组distance进行更新，
                //比较原路径长度与以新加入的顶点为中间点的路径长度
                distance[n] = distance[j] + g.edg[j][n];
                parent[n] = j;
            }
        }
    }    
    char ans [20];
    int dq=st,dw=en;
    int pathnum=0;
    ans[pathnum++] = g.ver[dw];
    
    while(g.ver[dw]!=g.ver[dq]){
        dw=parent[dw];
        ans[pathnum++] = g.ver[dw] ;
    } 
    printf("\n路径是：");
    for( i=pathnum-1; i>=0; i-- ){
        if(i==0){
            printf("%c", ans[i]);
            break;
        } else{
            printf("%c ---> ", ans[i]);
        }
    } 
    printf("\n\n");
    if(distance[en]==666){
        printf("无路径到达\n");
    } else{
        printf("%c到%c最短路径长度为: %d\n", g.ver[st], g.ver[en], distance[en]);
    }
    
}

int main(){
    Graph g;
    freopen("in.txt","r",stdin);//切文件输入数据;
    CreateGraph( &g );
    freopen("CON","r",stdin); //切换到从控制台输入数据;
    Dijkstra( g );
    return 0;
}