#include

#include

#include

#define Infinity 999  //最大值

#define Max_Vertex_Num 20  //顶点数最多为20

#define Len sizeof(struct arcNode)

#define gLen sizeof(struct Graph)

#define HIT_Ver_Num 11  //共有11个顶点

#define HIT_Arc_Num 18  //共有18个边

//边节点

struct arcNode{

    int adjvex;  //该边所指向的顶点位置

    struct arcNode *nextArc;  //指向下一条边的指针

    int value;  //边的权值

};

//顶点节点

typedef struct verNode{

    char *data;  //顶点信息

    struct arcNode *firstArc;  //指向第一条依附该顶点的边

}verNode,adjList[Max_Vertex_Num];

//图的邻接表存储类型

struct Graph{

    int g_arcs[Max_Vertex_Num][Max_Vertex_Num];

    adjList vertices;  //声明一个存储顶点的数组

    int vexNum,arcNum;  //vexNum 是顶点数，arcNum 是边数

};

struct Graph * creatGraph()

{

    int i,j,a,b;

    struct Graph *graph = (struct Graph *)malloc(gLen);

    struct arcNode *arc_1 = (struct arcNode *)malloc(Len);//N楼

    struct arcNode *arc_2 = (struct arcNode *)malloc(Len);

    struct arcNode *arc_3 = (struct arcNode *)malloc(Len);

    struct arcNode *arc_4 = (struct arcNode *)malloc(Len);//食堂

    struct arcNode *arc_5 = (struct arcNode *)malloc(Len);

    struct arcNode *arc_6 = (struct arcNode *)malloc(Len);

    struct arcNode *arc_7 = (struct arcNode *)malloc(Len);//教师公寓

    struct arcNode *arc_8 = (struct arcNode *)malloc(Len);

    struct arcNode *arc_9 = (struct arcNode *)malloc(Len);//M楼

    struct arcNode *arc_10 = (struct arcNode *)malloc(Len);

    struct arcNode *arc_11 = (struct arcNode *)malloc(Len);

    struct arcNode *arc_12 = (struct arcNode *)malloc(Len);//G楼

    struct arcNode *arc_13 = (struct arcNode *)malloc(Len);

    struct arcNode *arc_14 = (struct arcNode *)malloc(Len);

    struct arcNode *arc_15 = (struct arcNode *)malloc(Len);

    struct arcNode *arc_16 = (struct arcNode *)malloc(Len);

    struct arcNode *arc_17 = (struct arcNode *)malloc(Len);

    struct arcNode *arc_18 = (struct arcNode *)malloc(Len);//主楼

    struct arcNode *arc_19 = (struct arcNode *)malloc(Len);

    struct arcNode *arc_20 = (struct arcNode *)malloc(Len);

    struct arcNode *arc_21 = (struct arcNode *)malloc(Len);//H楼

    struct arcNode *arc_22 = (struct arcNode *)malloc(Len);

    struct arcNode *arc_23 = (struct arcNode *)malloc(Len);

    struct arcNode *arc_24 = (struct arcNode *)malloc(Len);//体育场

    struct arcNode *arc_25 = (struct arcNode *)malloc(Len);

    struct arcNode *arc_26 = (struct arcNode *)malloc(Len);

    struct arcNode *arc_27 = (struct arcNode *)malloc(Len);//校训石

    struct arcNode *arc_28 = (struct arcNode *)malloc(Len);

    struct arcNode *arc_29 = (struct arcNode *)malloc(Len);

    struct arcNode *arc_30 = (struct arcNode *)malloc(Len);

    struct arcNode *arc_31 = (struct arcNode *)malloc(Len);//研究院

    struct arcNode *arc_32 = (struct arcNode *)malloc(Len);

    struct arcNode *arc_33 = (struct arcNode *)malloc(Len);

    struct arcNode *arc_34 = (struct arcNode *)malloc(Len);//学校正门

    struct arcNode *arc_35 = (struct arcNode *)malloc(Len);

    struct arcNode *arc_36 = (struct arcNode *)malloc(Len);

    char *Data[HIT_Ver_Num] = {"N楼","食堂","教师公寓","M楼","G楼","主楼","H楼","体育场","校训石","研究院","学校正门"};

    if(graph==NULL||arc_1==NULL||arc_2==NULL||arc_3==NULL||arc_4==NULL||arc_5==NULL||arc_6==NULL||arc_7==NULL||arc_8==NULL||arc_9==NULL

       ||arc_10==NULL||arc_11==NULL||arc_12==NULL||arc_13==NULL||arc_14==NULL||arc_15==NULL||arc_16==NULL||arc_17==NULL||arc_18==NULL

       ||arc_19==NULL||arc_20==NULL||arc_21==NULL||arc_22==NULL||arc_23==NULL||arc_24==NULL||arc_25==NULL||arc_26==NULL||arc_27==NULL

       ||arc_28==NULL||arc_29==NULL||arc_30==NULL||arc_31==NULL||arc_32==NULL||arc_33==NULL||arc_34==NULL||arc_35==NULL||arc_36==NULL)

       {

           printf("内存不足\n退出程序");

           exit(0);

       }

    graph->vexNum = HIT_Ver_Num;

    graph->arcNum = HIT_Arc_Num;

    for(j = 0; j < graph->vexNum; j++)

    {

        graph->vertices[j].data = Data[j];

        graph->vertices[j].firstArc = NULL;

    }

    arc_1->value = 130;

    arc_1->adjvex = 3;

    arc_1->nextArc = graph->vertices[0].firstArc;

    graph->vertices[0].firstArc = arc_1;

    arc_2->value = 140;

    arc_2->adjvex = 4;

    arc_2->nextArc = graph->vertices[0].firstArc;

    graph->vertices[0].firstArc = arc_2;

    arc_3->value = 55;

    arc_3->adjvex = 1;

    arc_3->nextArc = graph->vertices[0].firstArc;

    graph->vertices[0].firstArc = arc_3;//End N楼

    arc_4->value = 55;

    arc_4->adjvex = 0;

    arc_4->nextArc = graph->vertices[1].firstArc;

    graph->vertices[1].firstArc = arc_4;

    arc_5->value = 150;

    arc_5->adjvex = 4;

    arc_5->nextArc = graph->vertices[1].firstArc;

    graph->vertices[1].firstArc = arc_5;

    arc_6->value = 110;

    arc_6->adjvex = 2;

    arc_6->nextArc = graph->vertices[1].firstArc;

    graph->vertices[1].firstArc = arc_6;//End 食堂

    arc_7->value = 110;

    arc_7->adjvex = 1;

    arc_7->nextArc = graph->vertices[2].firstArc;

    graph->vertices[2].firstArc = arc_7;

    arc_8->value = 105;

    arc_8->adjvex = 6;

    arc_8->nextArc = graph->vertices[2].firstArc;

    graph->vertices[2].firstArc = arc_8;//End 教师公寓

    arc_9->value = 130;

    arc_9->adjvex = 0;

    arc_9->nextArc = graph->vertices[3].firstArc;

    graph->vertices[3].firstArc = arc_9;

    arc_10->value = 40;

    arc_10->adjvex = 4;

    arc_10->nextArc = graph->vertices[3].firstArc;

    graph->vertices[3].firstArc = arc_10;

    arc_11->value = 70;

    arc_11->adjvex = 7;

    arc_11->nextArc = graph->vertices[3].firstArc;

    graph->vertices[3].firstArc = arc_11;//End M楼

    arc_12->value = 40;

    arc_12->adjvex = 3;

    arc_12->nextArc = graph->vertices[4].firstArc;

    graph->vertices[4].firstArc = arc_12;

    arc_13->value = 140;

    arc_13->adjvex = 0;

    arc_13->nextArc = graph->vertices[4].firstArc;

    graph->vertices[4].firstArc = arc_13;

    arc_14->value = 150;

    arc_14->adjvex = 1;

    arc_14->nextArc = graph->vertices[4].firstArc;

    graph->vertices[4].firstArc = arc_14;

    arc_15->value = 40;

    arc_15->adjvex = 5;

    arc_15->nextArc = graph->vertices[4].firstArc;

    graph->vertices[4].firstArc = arc_15;

    arc_16->value = 100;

    arc_16->adjvex = 8;

    arc_16->nextArc = graph->vertices[4].firstArc;

    graph->vertices[4].firstArc = arc_16;

    arc_17->value = 65;

    arc_17->adjvex = 7;

    arc_17->nextArc = graph->vertices[4].firstArc;

    graph->vertices[4].firstArc = arc_17;//End G楼

    arc_18->value = 40;

    arc_18->adjvex = 4;

    arc_18->nextArc = graph->vertices[5].firstArc;

    graph->vertices[5].firstArc = arc_18;

    arc_19->value = 115;

    arc_19->adjvex = 6;

    arc_19->nextArc = graph->vertices[5].firstArc;

    graph->vertices[5].firstArc = arc_19;

    arc_20->value = 50;

    arc_20->adjvex = 8;

    arc_20->nextArc = graph->vertices[5].firstArc;

    graph->vertices[5].firstArc = arc_20;//End 主楼

    arc_21->value = 105;

    arc_21->adjvex = 2;

    arc_21->nextArc = graph->vertices[6].firstArc;

    graph->vertices[6].firstArc = arc_21;

    arc_22->value = 115;

    arc_22->adjvex = 5;

    arc_22->nextArc = graph->vertices[6].firstArc;

    graph->vertices[6].firstArc = arc_22;

    arc_23->value = 60;

    arc_23->adjvex = 9;

    arc_23->nextArc = graph->vertices[6].firstArc;

    graph->vertices[6].firstArc = arc_23;//End H楼

    arc_24->value = 70;

    arc_24->adjvex = 3;

    arc_24->nextArc = graph->vertices[7].firstArc;

    graph->vertices[7].firstArc = arc_24;

    arc_25->value = 65;

    arc_25->adjvex = 4;

    arc_25->nextArc = graph->vertices[7].firstArc;

    graph->vertices[7].firstArc = arc_25;

    arc_26->value = 100;

    arc_26->adjvex = 10;

    arc_26->nextArc = graph->vertices[7].firstArc;

    graph->vertices[7].firstArc = arc_26;//End 体育场

    arc_27->value = 100;

    arc_27->adjvex = 4;

    arc_27->nextArc = graph->vertices[8].firstArc;

    graph->vertices[8].firstArc = arc_27;

    arc_28->value = 50;

    arc_28->adjvex = 5;

    arc_28->nextArc = graph->vertices[8].firstArc;

    graph->vertices[8].firstArc = arc_28;

    arc_29->value = 50;

    arc_29->adjvex = 9;

    arc_29->nextArc = graph->vertices[8].firstArc;

    graph->vertices[8].firstArc = arc_29;

    arc_30->value = 40;

    arc_30->adjvex = 10;

    arc_30->nextArc = graph->vertices[8].firstArc;

    graph->vertices[8].firstArc = arc_30;//End 校训石

    arc_31->value = 50;

    arc_31->adjvex = 8;

    arc_31->nextArc = graph->vertices[9].firstArc;

    graph->vertices[9].firstArc = arc_31;

    arc_32->value = 60;

    arc_32->adjvex = 6;

    arc_32->nextArc = graph->vertices[9].firstArc;

    graph->vertices[9].firstArc = arc_32;

    arc_33->value = 70;

    arc_33->adjvex = 10;

    arc_33->nextArc = graph->vertices[9].firstArc;

    graph->vertices[9].firstArc = arc_33;//End 研究院

    arc_34->value = 100;

    arc_34->adjvex = 7;

    arc_34->nextArc = graph->vertices[10].firstArc;

    graph->vertices[10].firstArc = arc_34;

    arc_35->value = 40;

    arc_35->adjvex = 8;

    arc_35->nextArc = graph->vertices[10].firstArc;

    graph->vertices[10].firstArc = arc_35;

    arc_36->value = 70;

    arc_36->adjvex = 9;

    arc_36->nextArc = graph->vertices[10].firstArc;

    graph->vertices[10].firstArc = arc_36;//End 学校正门

    for(a = 0; a < graph->vexNum; a++)  //置为无穷大（999）

    {

        for(b = 0; b < graph->vexNum; b++)

        {

            graph->g_arcs[a][b] = Infinity;

        }

    }

    for(i = 0; i < graph->vexNum; i++)  //将相应位置置权值

    {

        while(graph->vertices[i].firstArc != NULL)

        {

            graph->g_arcs[i][graph->vertices[i].firstArc->adjvex] = graph->vertices[i].firstArc->value;

            graph->vertices[i].firstArc = graph->vertices[i].firstArc->nextArc;

        }

    }

    return graph;

}

//单源最短路径(即 Dijkstra算法)

void shortestPath_Dij(struct Graph graph,int v0)

{

    int i = 0,v,w,min,pre;

    int arrayD[HIT_Ver_Num],arrayP[HIT_Ver_Num];//辅助数组

    int arrayFinal[HIT_Ver_Num];//辅助数组

    //初始化

    for(v = 0; v < graph.vexNum; v++)

    {

        arrayFinal[v] = 0;

        arrayD[v] =graph.g_arcs[v0][v];

        if(arrayD[v] < Infinity)

        {

            arrayP[v] = v0;

        }

        else

        {

            arrayP[v] = -1;

        }

    }

    arrayFinal[v0] = 1;

    arrayP[v0] = -1;

    for(i = 1; i < graph.vexNum; i++)

    {

        min = Infinity;

        //加入具有最小代价的邻居节点

        for(w = 0; w < graph.vexNum; w++)

        {

            if(!arrayFinal[w] && (arrayD[w] < min))

            {

                v = w;

                min = arrayD[w];

            }

        }

        arrayFinal[v] = 1;

        //计算加入新的节点后，更新路径使得其产生代价最短

        for(w = 0; w < graph.vexNum; w++)

        {

            if(!arrayFinal[w] && (min + graph.g_arcs[v][w] < arrayD[w]))

            {

                arrayD[w] = min + graph.g_arcs[v][w];

                arrayP[w] = v;

            }

        }

    }

    for(i = 0; i < graph.vexNum; i++)

    {

        if(v0 == i)

            printf("目的地与起点重合，权值为零\n\n");

        else

        {

            printf("权值为：%d\n",arrayD[i]);

            printf("%s",graph.vertices[i].data);

            pre = arrayP[i];

            while(pre != -1)

            {

                printf(" <-- %s",graph.vertices[pre].data);

                pre = arrayP[pre];

            }

            printf("\n\n");

        }

    }

}

void shortestPath_Floyd(struct Graph graph,int v1,int v2)

{

    int i,j,k,temp;

    int arrayPath[HIT_Ver_Num][HIT_Ver_Num],arrayDis[HIT_Ver_Num][HIT_Ver_Num];

    //初始化

    for(i = 0; i < graph.vexNum; i++)

    {

        for(j = 0; j < graph.vexNum; j++)

        {

            if(graph.g_arcs[i][j] < Infinity)

                arrayPath[i][j] = j;

            else

                arrayPath[i][j] = -1;

            arrayDis[i][j] = graph.g_arcs[i][j];

        }

    }

    for(k = 0; k < graph.vexNum; k++)//对所有顶点进行试探

    {

        for(i = 0; i < graph.vexNum; i++)

        {

            for(j = 0; j < graph.vexNum; j++)

            {

                if(arrayDis[i][j] > arrayDis[i][k] + arrayDis[k][j])

                {

                    arrayDis[i][j] = arrayDis[i][k] + arrayDis[k][j];//取较小者

                    arrayPath[i][j] = arrayPath[i][k];//改Vi的后继

                }

            }

        }

    }

    printf("从 %s 到 %s 的最短距离为：%d\n",graph.vertices[v1].data,graph.vertices[v2].data,arrayDis[v1][v2]);

    printf("最短路径为：\t");

    temp = arrayPath[v1][v2];

    printf("%s --> ",graph.vertices[v1].data);//输出V1

    while(temp != v2)//temp不等于路径终点v2时

    {

        printf("%s --> ",graph.vertices[temp].data);//输出

        temp = arrayPath[temp][v2];//求路径上下一顶点

    }

    printf("%s.",graph.vertices[v2].data);//输出V2

    printf("\n");

}

int main()

{

    int b,c,count = 0;

    int num,i,a,i_2,i_3;

    char *nodeName_1 = (char*)malloc(10);//必须得用malloc函数申请空间

    char *nodeName_2 = (char*)malloc(10);//必须得用malloc函数申请空间

    char *nodeName_3 = (char*)malloc(10);//必须得用malloc函数申请空间

    struct Graph *graph;

    graph = creatGraph();  //生成图

    for(b=0;bvexNum;b++)

    {

        for(c = 0;cvexNum;c ++)

        {

            printf("%d\t",graph->g_arcs[b][c]);

        }

        printf("\n");

    }

    printf("请按提示进行操作:\n");

    printf("1、输入任意一个节点的名称，显示它到各个节点的最短路径及最短距离。\n");

    printf("2、输入任意两个节点的名称，显示两点间最短路径和最短距离。\n");

    printf("请输入 1 或 2 进行查询。\n");

    scanf("%d",&num);

    switch(num)

    {

        case 1:

            for(a = 0;avexNum;a++)

            {

                printf("%s ",graph->vertices[a].data);

            }

            printf("\n");

            printf("请输入节点名称：\n");

            scanf("%s",nodeName_1);

            for(i = 0; i < graph->vexNum; i++)

            {

                if(strcmp(nodeName_1,graph->vertices[i].data) != 0)

                {

                    count++;

                }

                if(0 == strcmp(nodeName_1,graph->vertices[i].data))

                {

                    shortestPath_Dij(*graph,i);

                }

            }

            if(graph->vexNum == count)

            {

                printf("输入名称有误！退出程序！");

                exit(0);

            }

        break;

        case 2:

            for(a = 0;avexNum;a++)

            {

                printf("%s ",graph->vertices[a].data);

            }

            printf("\n");

            printf("请分别输入第一个节点名称：\n");

            scanf("%s",nodeName_2);

            printf("请分别输入第二个节点名称：\n");

            scanf("%s",nodeName_3);

            for(i = 0; i < graph->vexNum; i++)

            {

                if(0 == strcmp(nodeName_2,graph->vertices[i].data))

                {

                    i_2 = i;

                }

                if(0 == strcmp(nodeName_3,graph->vertices[i].data))

                {

                    i_3 = i;

                }

            }

            if(i_2 == i_3)

            {

                printf("输入的起点和终点重合，退出程序！");

                exit(0);

            }

            shortestPath_Floyd(*graph,i_2,i_3);

        break;

        default:

            printf("输入有误！退出程序！");

            exit(0);

        break;

    }

    return 0;

}