资源描述：
《利用Dijstra算法求图或网中给定两顶点间的最短路径.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、利用Dijkstra算法求图或网中给定两顶点间的最短路径作者：人生休憩提交日期：2006-6-123:25:00利用Dijkstra算法求图或网中给定两顶点间的最短路径程序源代码#include#include#include#defineINFINITY32767/*用整型最大值代替∞*/#defineMAX_VERTEX_NUM20/*最大顶点个数*/#defineMAX_NAME5/*顶点字符串的最大长度*//*图的邻接矩阵存储表示*/typedefintVRType;typedefcharVertexType[
2、MAX_NAME];typedefintPathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefintShortPathTable[MAX_VERTEX_NUM];typedefenum{DG,DN,AG,AN}GraphKind;/*{有向图,有向网,无向图,无向网}*/typedefstruct{VRTypeadj;/*顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；对带权图，则为权值类型*/}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
3、typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];/*顶点向量*/AdjMatrixarcs;/*邻接矩阵*/intvexnum,arcnum;/*图的当前顶点数和弧数*/GraphKindkind;/*图的种类标志*/}MGraph;intLocateVex(MGraphG,VertexTypeu){/*初始条件:图G存在,u和G中顶点有相同特征*//*操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/inti;for(i=0;i4、if(strcmp(u,G.vexs[i])==0)returni;return-1;}/*采用数组(邻接矩阵)表示法,构造有向图G*/intCreateDG(MGraph*G){inti,j,k;VertexTypeva,vb;printf("请输入有向图G的顶点数,弧数(中间用逗号隔开):");scanf("%d,%d",&(*G).vexnum,&(*G).arcnum);printf("请分别输入%d个顶点的值(<%d个字符):",(*G).vexnum,MAX_NAME);for(i=0;i<(*G)
5、.vexnum;i++)/*构造顶点向量*/scanf("%s",(*G).vexs[i]);for(i=0;i<(*G).vexnum;i++)/*初始化邻接矩阵*/for(j=0;j<(*G).vexnum;j++)(*G).arcs[i][j].adj=0;/*图*/printf("请分别输入%d条弧的弧头、弧尾(以空格作为间隔):",(*G).arcnum);for(k=0;k<(*G).arcnum;++k){scanf("%s%s%*c",va,vb);/*%*c吃掉回车符*/i=LocateVex(*G,va
6、);j=LocateVex(*G,vb);(*G).arcs[i][j].adj=1;/*有向图*/}(*G).kind=DG;return1;}/*采用数组(邻接矩阵)表示法,构造有向网G*/intCreateDN(MGraph*G){inti,j,k,w;VertexTypeva,vb;printf("请输入有向网G的顶点数,弧数(中间用逗号隔开):");scanf("%d,%d",&(*G).vexnum,&(*G).arcnum);printf("请分别输入%d个顶点的值(<%d个字符):",(
7、*G).vexnum,MAX_NAME);for(i=0;i<(*G).vexnum;i++){/*构造顶点向量*/scanf("%s",(*G).vexs[i]);//printf("");}printf("请分别输入%d条弧的弧头、弧尾、权值(以空格作为间隔):",(*G).arcnum);for(i=0;i<(*G).vexnum;i++)/*初始化邻接矩阵*/for(j=0;j<(*G).vexnum;j++)(*G).arcs[i][j].adj=INFINITY;/*网*/for(k=0;k<(*G).
8、arcnum;k++)
