#include <stdio.h>             #define INFINITY 65535  typedef int VertexType; //頂點(diǎn)是字符型 typedef int EdgeType; //邊是整型 typedef struct //圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu) {   VertexType vexs[9]; //頂點(diǎn)向量   EdgeType edges[9][9];  //鄰接矩陣   int vexnum,arcnum; //圖中當(dāng)前的頂點(diǎn)數(shù)和邊數(shù)  }MGraph;  /* 鄰接矩陣的建立*/  void CreateGraph(MGraph *G) {   int i,j,k,weight;  int ch1,ch2;   printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)(輸入格式為:頂點(diǎn)數(shù),邊數(shù)):");   scanf("%d,%d",&(G->vexnum),&(G->arcnum));   printf("請(qǐng)輸入頂點(diǎn)名稱(chēng)(輸入格式為:a,b,c...)：");   for(i=0;i<G->vexnum;i++)  {   getchar();   scanf("%d",&(G->vexs[i]));  }     for(i=0;i<G->vexnum;i++)   for(j=0;j<G->vexnum;j++)    if(i==j)     G->edges[i][j]=0;    else     G->edges[i][j]=INFINITY;    printf("請(qǐng)輸入每條邊對(duì)應(yīng)的兩個(gè)頂點(diǎn)名稱(chēng)(輸入格式為:a,b):/n");    for(k=0;k<G->arcnum;k++)   {    // getchar();    printf("請(qǐng)輸入第%d條邊的兩個(gè)頂點(diǎn)名稱(chēng)：",k+1);    scanf("%d,%d",&ch1,&ch2);    for(i=0;ch1!=G->vexs[i];i++);    for(j=0;ch2!=G->vexs[j];j++);    getchar();    printf("請(qǐng)輸入第%d條邊的權(quán)值：",k+1);    scanf("%d",&weight);     G->edges[i][j]=weight;    G->edges[j][i]=weight;   }   }  void ShortestPath_Floyd(MGraph G,int P[9][9],int D[9][9]) {  int v,w,k;  for(v=0;v<G.vexnum;v++)//初始化D和P  {   for(w=0;w<G.vexnum;w++)   {    D[v][w]=G.edges[v][w];    P[v][w]=w;   }  }    for(k=0;k<G.vexnum;k++)  {   for(v=0;v<G.vexnum;v++)   {    for(w=0;w<G.vexnum;w++)    {     if(D[v][w]>(D[v][k]+D[k][w]))     {//如果經(jīng)過(guò)下標(biāo)為k頂點(diǎn)路徑比原兩點(diǎn)間路徑更短，將當(dāng)前兩點(diǎn)間權(quán)值設(shè)為更小的一個(gè)     D[v][w]=D[v][k]+D[k][w];     P[v][w]=P[v][k];     }         }   }  } } void main() {  MGraph G;  CreateGraph(&G);  int i,j;  printf("edgesnum:%d/n",G.arcnum);  printf("vexesnum:%d/n",G.vexnum);  for(i=0;i<9;i++)  {   for(j=0;j<9;j++)    printf("%d ",G.edges[i][j]);   printf("/n");  }  int v,w,k;  int P[9][9];  int D[9][9];  printf("%d/n",P);  printf("%d/n",D);  ShortestPath_Floyd(G,P,D);  for(v=0;v<G.vexnum;v++)//顯示路徑  {   for(w=v+1;w<G.vexnum;w++)   {    printf("v%d-v%d weight:%d ",v,w,D[v][w]);    k=P[v][w];    printf("path:%d",v);    while(k!=w)    {     printf("->%d",k);     k=P[k][w];    }    printf("->%d/n",w);   }  } }