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

#define MVnum 100   //最大顶点数
#define Maxint 32767 //定义计算机中的int的最大值


typedef enum {FALSE,TRUE} boolean;
typedef struct  
{//建立图的存储结构
    char vexs[MVnum];     //顶点数组
    int arcs[MVnum][MVnum];   //邻接矩阵
}MGraph;

int D1[MVnum],P1[MVnum];
int D[MVnum][MVnum];
int P[MVnum][MVnum];

void createMGraph(MGraph *G,int n,int e);
void Dijkstra(MGraph G,int v1,int n);
void Floyd(MGraph G,int n);

int main()
{
    MGraph G;
    int n,e,v,w,k;
    int xz = 1;
    printf("请输入图中顶点个数和边数n,e： ");
    scanf("%d,%d",&n,&e);
    createMGraph(&G,n,e);
    while(xz != 0)
    {
        printf("\n");
        printf("******求城市之间的最短路径******\n");
        printf("================================\n");
        printf("1.求一个城市到所有城市的最短路径\n");
        printf("2.求任意的两个城市之间的最短路径\n");
        printf("================================\n");
        printf(" 请选择: 1 或 2，选择 0 退出 ：   ");
        scanf("%d",&xz);
        
        if(xz == 2)
        {
            Floyd(G,n);   //调用佛洛依德算法
            printf("请输入源点(起点)和终点: v,w: ");
            scanf("%d,%d",&v,&w);
            k = P[v][w];
            if(k == 0)
            printf("顶点%d到%d没有路径!\n\n",v,w);
            else
            {
                printf("从顶点%d到%d的最短路径是：%d",v,w,v);
             while(k != w)
             {
                 printf("->%d",k); //输出后继顶点
                 k = P[k][w];      //继续寻找下一个后继顶点
             }
             printf("->%d\n",w);  //输出终点w
             printf("  路径长度: %d\n\n",D[v][w]);
              }
            }
            else
            if(xz == 1)
            {
                printf("求单源路径，请输入源点 v :");
                scanf("%d",&v);
                printf("\n");
                Dijkstra(G,v,n); //调用Dijkstra算法
            }
        }
        printf("\n");
        printf("结束!谢谢使用!\n");
        return 0;
        }



void createMGraph(MGraph *G,int n,int e)
{
//采用邻接矩阵构建有向图，n表示定点数，e表示变数
    int i,j,k,w;
    for(i = 1;i < n;i ++)
    G -> vexs[i] = (char)i;
    for(i = 1;i < n + 1;i ++)
    for(j = 1;j < n + 1;j ++)
    {
        G -> arcs[i][j] = Maxint;   //初始化邻接矩阵
    }
    printf("输入%d条边的i,j及w：\n\n",e);
    for(k = 1;k < e + 1;k ++)
    {
        scanf("%d,%d,%d",&i,&j,&w);
        G -> arcs[i][j] = w;
    }
    printf("有向图的存储结构构建完毕!\n\n");
    
}




void Dijkstra(MGraph G,int v1,int n)
{
    int D2[MVnum];
    int P2[MVnum];
    int v,i,w,min;
    boolean S[MVnum];
    for(v = 1;v < n + 1;v ++)
    {
        S[v] = FALSE;;     //置空最短路径终点集
        D2[v] = G.arcs[v1][v];
        if(D2[v] < Maxint)
        P2[v] = v1;        //v1是v的前驱
        else
        P2[v] = 0;         //v没有前驱
    }
    
    D2[v1] = 0;         //s集初始时只有源点，源点到源点的距离为0
    S[v1] = TRUE;
    
    for(i = 2;i < n;i ++)
    {
    min = Maxint;
    for(w = 1;w < n + 1;w ++)
    if(!S[w] && D2[w] < min)
    {
        v = w;
        min = D2[w];
    }
    S[v] = TRUE;
    for(w = 1;w < n + 1;w ++)
    {
        if(!S[w] && (D2[v] + G.arcs[v][w] < D2[w]))
        {
            D2[w] = D2[v] + G.arcs[v][w];
            P2[w] = v;
        }
    }
        printf("路径长度     路径\n");
        
        for(i = 1;i < n + 1;i ++)
        {
            printf("%9d",D2[i]);
            printf("%9d",i);
            v = P2[i];
            while(v != 0)
            {
                printf("<-%d",v);
                v = P2[v];
            }
            printf("\n");
        }
}
}



void Floyd(MGraph G,int n)
{
    //int n;
    int i;
    int j;
    int k;
    for(i = 1;i < n + 1;i ++)
    for(j = 1;j < n + 1;j ++)
    {
        if(G.arcs[i][j] != Maxint)
        P[i][j] = j;
        else
        P[i][j] = 0;
        D[i][j] = G.arcs[i][j];
    }
    
    for(k = 1;k < n + 1;k ++)
    {
        for(i = 1;i < n + 1;i ++)
        for(j = 1;j < n + 1;j ++)
        {
            if(D[i][k] + D[k][j] < D[i][j])
            {
                D[i][j] = D[i][k] + D[k][j];
                P[i][j] = P[i][k];
            }
        }
    }
}