- #include <stdio.h>
- #define MAXV 100 /*最大顶点个数*/
- #define INF 32767 /*用32767表示∞*/
- typedef int InfoType;
- /*以下定义邻接矩阵类型*/
- typedef struct
- {
- int no; /*顶点编号*/
- InfoType info; /*顶点其他信息*/
- } VertexType; /*顶点类型*/
- typedef struct /*图的定义*/
- { int edges[MAXV][MAXV]; /*邻接矩阵*/
- int vexnum,arcnum; /*顶点数,弧数*/
- VertexType vexs[MAXV]; /*存放顶点信息*/
- } MGraph; /*图的邻接矩阵类型*/
- void DispMat(MGraph g) /*输出邻接矩阵g*/
- {
- int i,j;
- for (i=0;i<g.vexnum;i++)
- {
- for (j=0;j<g.vexnum;j++)
- if (g.edges[i][j]==INF)
- printf("%3s","∞");
- else
- printf("%3d",g.edges[i][j]);
- printf("\\n");
- }
- }
- void DisPath(int path[],int v0,int u) /*由path计算最短路*/
- {
- int count=0;
- int m=0;
- int way[MAXV];
- int w=u;
- while(w!=v0)
- {
- way[count]=path[w];
- count=count+1;
- w=path[w];
- }
- printf("最短路径:");
- for (m=count-1;m>=0;m--) //逆向输出路径数组way[]
- {
- printf("%d->",way[m]);
- }
- printf("%d\\n",u);
- }
- void Dijkstra(MGraph g,int v0) /*从顶点v0到其余各顶点的最短路径*/
- {
- int n;
- n=g.vexnum;
- int dist[MAXV], path[MAXV]; //dist[]表示已经找到的且从原点到每个点的最短路径的长度 ,path[]存放当前最短路径
- int s[MAXV]={0};
- printf("输出最短路径:\\n");
- int i,j,min,u;
- path[v0]=v0; //顶点的前驱节点是自己
- for (i=0;i<n;i++)
- {
- dist[i]=g.edges[v0][i];
- path[i]=v0;
- }
- u=v0; //u作为中转节点,
- for (i=0;i<n;i++)
- {
- for (j=0;j<n;j++) //计算以u为中转点,v到各顶点的权值
- {
- if (dist[j]>dist[u]+g.edges[u][j])
- {
- dist[j]=dist[u]+g.edges[u][j];
- path[j]=u;
- }
- }
- min=INF;
- for (j=0;j<n;j++)
- {
- if ((s[j]==0) && (dist[j]<min))
- {
- min=dist[j];
- u=j;
- }
- }
- s[u]=1;
- }
- for(i=0;i<n;i++)
- {
- if (i!=0)
- {
- printf("\\n狄克斯特拉算法:\\n<%d,%d>is %d,",v0,i,dist[i]);
- DisPath(path,v0,i); /*输出最短路径*/
- }
- }
- }
- void main()
- {
- int i,j,u=0;
- MGraph g;
- int A[MAXV][6]={
- {INF,5,INF,7,INF,INF},
- {INF,INF,4,INF,INF,INF},
- {8,INF,INF,INF,INF,9},
- {INF,INF,5,INF,INF,6},
- {INF,INF,INF,5,INF,INF},
- {3,INF,INF,INF,1,INF}};
- g.vexnum=6;g.arcnum=10;
- for (i=0;i<g.vexnum;i++) /*建立图9.1的邻接矩阵*/
- for (j=0;j<g.vexnum;j++)
- g.edges[i][j]=A[i][j];
- printf("\\n");
- printf("有向图G的邻接矩阵:\\n");
- DispMat(g);
- printf("\\n");
- printf(":\\n");
- Dijkstra(g,u);
- printf("\\n");
- }
- //该片段来自于http://www.codesnippet.cn/detail/261120137489.html
来源: http://www.codesnippet.cn/detail/261120137489.html