- #include <stdio.h>
- #include<malloc.h>
- #include <stdlib.h>
- #define MaxVerNum 30//定义存储的最大个数
- #define NIF 32767 //定义无穷大
- #define false 0
- #define true 1
- typedef char VertexType;//定义顶点表类型是字符型
- typedef int Edgetype;
- /**建立结构体**/
- typedef struct{
- VertexType vexs[MaxVerNum];/*顶点表*/
- Edgetype edges[MaxVerNum][MaxVerNum];//边表
- int n,e; //顶点数和边数
- }MGraph;
- /**初始化有向图的邻接矩阵存储**/
- void CreatGraph(MGraph *G)
- { /**接口参数:图的结构体指针**/
- int i,j,k;
- printf("How many City and Path?\\t(example:4,5):\\t");
- scanf("%d,%d",&(G->n),&(G->e));//顶点数及边数
- printf("\\nInput each City's information .\\n");
- for(i=0;i<G->n;i++)
- {
- scanf("%s",&(G->vexs[i]));/**输入顶点信息**/
- }
- for(i=0;i<G->n;i++)
- for(j=0;j<G->n;j++)
- {
- if(i==j) G->edges[i][j]=0;
- else G->edges[i][j]=NIF; /**对角线为0,其他为无穷大**/
- }
- for(k=0;k<G->e;k++)
- {
- printf("\\nInput two Cities include this path(eg:2,3):\\t");
- scanf("%d,%d",&i,&j);/**输入边的信息**/
- printf("\\nThen input its weigth:");
- scanf("%d",&(G->edges[i][j]));/***权值***/
- }
- /*****************输出建立好的矩阵********************/
- printf("\\n==>HAHA!We can easily get this matrix from your input<==\\n\\n");
- for(i=0;i<G->n;i++)
- {
- printf("%5c",G->vexs[i]);
- printf("\\t ");
- }
- printf("\\n _________________________________________________\\n");
- for(i=0;i<G->n;i++)
- {
- printf("%c|",G->vexs[i]);
- for(j=0;j<G->n;j++)
- {
- printf("%5d ",G->edges[i][j]);
- if(j==G->n-1)
- printf(" |\\n");
- }
- }
- printf(" -------------------------------------------------\\n");
- }
- /***Dijkstra:求得最短路径***/
- int Dijkstra(MGraph *G,int v0)
- {
- int D[MaxVerNum];/**存储v0分别到每个顶点的最短路径**/
- int final[MaxVerNum];/**记录是否在D中**/
- int i,v,w,min;
- for(v=0;v<G->n;++v)
- {
- final[v]=false;
- D[v]=G->edges[v0][v];
- }
- D[v0]=0;
- final[v0]=true;/**v0属于S集**/
- for(i=1;i<G->n;++i)
- {
- min=NIF;
- for(w=0;w<G->n;++w)
- if(!final[w]&&D[w]<min)
- {
- v=w;
- min=D[w];
- }
- final[v]=true;
- for(w=0;w<G->n;++w)
- {
- if(!final[w]&&(min+G->edges[v][w]<D[w]))
- {
- D[w]=min+G->edges[v][w];
- }
- }
- }
- printf("\\nThe shortest path from $$$> %c <$$$ to each destination is:\\n\\n",G->vexs[v0]);
- for(i=0;i<G->n;i++)
- {
- printf("%5c",G->vexs[i]);
- printf("\\t "); /**此部分实现可视化**/
- }
- printf("\\n _______________________________________________\\n");
- printf("%c|",G->vexs[v0]);
- for(w=0;w<G->n;w++)
- printf("%5d |",D[w]);
- printf("\\n -----------------------------------------------\\n");
- return 1;
- }//:~
- /**Floyd求得各顶点间最短路径**/
- int Floyd(MGraph *G,int n)
- {
- int P[MaxVerNum][MaxVerNum][MaxVerNum];
- int D[MaxVerNum][MaxVerNum];
- int u,v,w,i;
- for(v=0;v<G->n;++v)
- for(w=0;w<G->n;++w)
- {
- D[v][w]=G->edges[v][w];
- for(u=0;u<G->n;++u)
- P[v][w][u]=0;
- if(D[v][w]<NIF)
- {
- P[v][w][v]=1;
- P[v][w][w]=1;
- }//if
- }//for
- for(u=0;u<G->n;++u)
- for(v=0;v<G->n;++v)
- for(w=0;w<G->n;++w)
- if(D[v][u]+D[u][w]<D[v][w])
- {
- D[v][w]=D[v][u]+D[u][w];
- for(i=0;i<G->n;++i)
- P[v][w][i]=P[v][u][i]||P[u][w][i];
- }
- /*********输出最后结果***********/
- for(i=0;i<G->n;i++)
- {
- printf("%5c",G->vexs[i]);
- printf("\\t ");
- }
- printf("\\n\\nAfter search,we can get this minumum matrix.\\n\\n");
- for(i=0;i<G->n;i++)
- {
- printf("%5c",G->vexs[i]);
- printf("\\t ");
- }
- printf("\\n _______________________________________________\\n");
- for(i=0;i<G->n;i++)
- {
- printf("%c|",G->vexs[i]);
- for(v=0;v<G->n;v++)
- {
- if(!D[i][v]||D[i][v]==NIF) printf("-----\\t");
- else printf("%5d \\t",D[i][v]);
- if(v==G->n-1)
- printf(" |\\n");
- }
- }
- printf(" -----------------------------------------------\\n");
- /********************输出最短路径*******************************/
- printf("\\nThis matrix can tell us the path to each destintion\\n");
- for(i=0;i<G->n;i++)
- {
- printf("%5c",G->vexs[i]);
- printf("\\t ");
- }
- printf("\\n _________________________________________________\\n");
- for(i=0;i<G->n;i++)
- {
- printf("%c|",G->vexs[i]);
- for(u=0;u<G->n;u++)
- {
- printf("%5d ",P[i][u][i]);
- if(u==G->n-1)
- printf(" |\\n");
- }
- }
- printf(" -------------------------------------------------\\n");
- /***************************************************************/
- return 1;
- }
- /**************主函数部分***************/
- int main()
- {
- int m;
- int ch;
- MGraph *S;
- S=(MGraph*)malloc(sizeof(MGraph));
- printf("\\t***************************************************\\n");
- printf("\\t*\\t WELCOME TO USE OUR SMART SYSTEM \\t *\\n");
- printf("\\t*\\tWe would try our best to serve for you! *\\n");
- printf("\\t***************************************************\\n");
- poin1:/**跳转作用**/
- printf("\\n\\t What can I do for you sir?\\n");
- printf("---------------------------------------------------\\n");
- printf("|1.Creat a graph\\n|2.Search the shortest path\\n");
- printf("|3.Find the shortest path between each two solutin\\n");
- printf("|4.exit system!\\n");
- printf("---------------------------------------------------\\n");
- printf("Input here please:\\t");
- scanf("%d",&ch);
- switch(ch)
- {
- /**********调用创建邻接矩阵函数***********/
- case 1: CreatGraph(S);goto poin1;
- /************调用Djkstra函数************/
- case 2:
- printf("\\nWhere are you now?[tips==>(0~5) stand for (a~f)]:");
- scanf("%d",&m);
- Dijkstra(S,m);goto poin1;
- /*************调用Floyd函数*************/
- case 3:
- Floyd(S,S->n);goto poin1;
- case 4:
- return 0;break;//直接推出系统
- default:
- printf("\\n\\tWarning!!!==>Input errer!Try again please!\\n");
- goto poin1;
- }
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/100320148931.html
来源: http://www.codesnippet.cn/detail/100320148931.html