#include <stdio.h>

#define MAXVEX 9
#define MAXEDGES 16
#define INFINITE 60000

//定义图的类型
typedef struct {
    int vexs[MAXVEX];//保存顶点名称
    int arc[MAXVEX][MAXVEX];//邻接矩阵
    int numVertexs,numEdges;
}MGraph;

typedef int Patharc[MAXVEX];    //存储最短路径的情况下，每个顶点的上一个顶点
typedef int ShortPathTable[MAXVEX];    //存储v0到各个顶点最短路径的长度

//构建图
void CreateMGraph(MGraph * G){
    int i,j;
    G->numEdges=16;
    G->numVertexs=9;
    //给每个顶点命名
    for(i=0; i<G->numVertexs; i++){
        G->vexs[i]=i;
    }

    for(i=0; i<G->numVertexs; i++){
        for(j=0; j<G->numVertexs; j++){
            if(i==j){
                G->arc[i][j]=0;
            }else{
                G->arc[i][j]=INFINITE;
            }
        }
    }

    G->arc[0][1]=1;
    G->arc[0][2]=5; 
    G->arc[1][2]=3; 
    G->arc[1][3]=7; 
    G->arc[1][4]=5; 

    G->arc[2][4]=1; 
    G->arc[2][5]=7; 
    G->arc[3][4]=2; 
    G->arc[3][6]=3; 
    G->arc[4][5]=3;

    G->arc[4][6]=6;
    G->arc[4][7]=9; 
    G->arc[5][7]=5; 
    G->arc[6][7]=2; 
    G->arc[6][8]=7;

    G->arc[7][8]=4;

    for(i=0;i<G->numVertexs; i++){
        for(j=0; j<i; j++){
            G->arc[i][j]=G->arc[j][i];
        }
    }
}

/*  Dijkstra算法，求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v] */    
/*  P[v]的值为前驱顶点下标,D[v]表示v0到v的最短路径长度和 */  
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D){
    int i,j,k,w;
    int final[MAXVEX];//如果找到到某顶点的最短路径，就标记1，初始为-1

    for(i=0; i<G.numVertexs; i++){
        (*P)[i]=0;//初始P[]为0
        final[i]=-1;
        (*D)[i]=G.arc[0][i];//初始化顶点0到其他顶点的长度
    }

    final[0]=1;//到0的最短路径已经找到了，就是本身
    

    for(i=1; i<G.numVertexs; i++){//以下的1，2，3，步骤，每进行一次会确定一个不同的顶点，
        //使得v0到该顶点的距离最短，如此循环G.numVertexs-1次，可以找到v0到其余所有顶点的最短路径
        
        //1.找v0到各个顶点最短的路径
        int min=INFINITE;
        for(j=1; j<G.numVertexs; j++){
            if(final[j]!=1 && (*D)[j] < min){
                min=(*D)[j];
                k=j;
            }
        }

        //2.顶点k的最短路径已经找到，就是min(找到一个做一次标记)
        final[k]=1;
        
        //3. 如果经过v顶点的路径比现在这条路径的长度短的话，更新v0到该顶点的距离，否则不进行任何操作
        for(w=1; w<G.numVertexs; w++){
            if(final[w]!=1 && min+G.arc[k][w] < (*D)[w]){
                /*  说明找到了更短的路径，修改D[w]和P[w] */
                (*D)[w]=min+G.arc[k][w];
                (*P)[w]=k;
            }
        }

    }
}

int main(){

MGraph G;
int i,j,t,v0=0;
Patharc P;
ShortPathTable D;

CreateMGraph(&G);

ShortestPath_Dijkstra(G, v0, &P, &D);

    //打印
    for(j=1; j<G.numVertexs; j++){

        printf("v%d-->v%d的最短路径长度为%d\n",v0,j,D[j]);
        
        t=j;
        printf("最短路径倒叙为v%d-->",t);
            while(P[t]!=0){
            printf("v%d-->",P[t]);
            t=P[t];
            }
        printf("v%d\n\n",P[t]);
    }
return 0;
}