1 # include 
     
        2   3 # define MAX_VERTEXES 20//最大顶点数  4 # define INFINITY 65535;//代表∞  5   6 typedef struct  7 {
   /*    无向图结构体    */  8     int vexs[MAX_VERTEXES];//顶点下标  9     int arc[MAX_VERTEXES][MAX_VERTEXES];//矩阵 10     int numVertexes, numEdges;//顶点数和边数 11  12 }MGraph; 13  14 typedef int PathArc[MAX_VERTEXES];//存储最短路径的下表数组 15 typedef int ShortPathTable[MAX_VERTEXES];//存储最短路径的权值数组 16  17 void CreateMGraph (MGraph *G) 18 {
   /*    创建 */ 19     int i, j; 20  21     //printf ("请输入顶点数和边数"); 22     G->numVertexes = 9;//顶点 23     G->numEdges = 16;//边 24  25     for (i=0; i
      
       numVertexes; i++) 26         G->vexs[i] = i;//初始化顶点下标 27  28     for (i=0; i
       
        numVertexes; i++)//初始化矩阵 29         for (j=0; j
        
         numVertexes; j++) 30             if (i == j) 31                 G->arc[i][j] = 0;//本身则0 32             else 33                 G->arc[i][j] = INFINITY;//否则为∞ 34  35     //提前手动输入 36     G->arc[0][1]=1; 37     G->arc[0][2]=5;  38     G->arc[1][2]=3;  39     G->arc[1][3]=7;  40     G->arc[1][4]=5;  41  42     G->arc[2][4]=1;  43     G->arc[2][5]=7;  44     G->arc[3][4]=2;  45     G->arc[3][6]=3;  46     G->arc[4][5]=3; 47  48     G->arc[4][6]=6; 49     G->arc[4][7]=9;  50     G->arc[5][7]=5;  51     G->arc[6][7]=2;  52     G->arc[6][8]=7; 53  54     G->arc[7][8]=4; 55  56     for (i=0; i
         
          numVertexes; i++)//无向图--矩阵上三角对称下三角 57         for (j=i; j
          
           numVertexes; j++) 58 if (i != j) 59 G->arc[j][i] = G->arc[i][j]; 60 61 return ; 62 63 } 64 65 //P数组-存放最短路径顶点的下标，D数组-存放最短路径(权值) 66 void Shorsequence_Path_Dijkstra (MGraph G, int v0, PathArc *P, ShortPathTable *D) 67 { /* 迪杰斯特拉 算法 - 生成最短路径 */ 68 int v, w, k, min; 69 int final[MAX_VERTEXES]; //final[w] = 1,表示求得顶点v0→vw的最短路径 70 71 for (v=0; v