离散数学小论文.doc

用编程求最短路径喆赫 20091101358数学科学学院 信息与计算科学 2009级1班指导教师 冯世斌摘 要 最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。 算法具体的形式包括；确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题。确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径。 全局最短路径问题 - 求图中所有的最短路径。关键词 编程;离散数学;最短路径;图论用于解决最短路径问题的算法被称作“最短路径算法”， 有时被简称为“路径算法”。1最短路径算法1.1最短路径常用算法最常用的路径算法有：Dijkstra算法、A*算法、SPFA算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法等。1.2 最短路径单元问题所谓单源最短路径问题是指：已知图G(V，E)，我们希望找出从某给定的源结点SV到V中的每个结点的最短路径。 首先，我们可以发现有这样一个事实：如果P是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路2用编程求最短路径问题 以下给出了用C语言编写的使用Dijkstra算法求最短路径问题的源代码：#includestdio.h#includestring.h#includemalloc.h#includestdlib.htypedef char VertexType4;typedef char InfoPtr;typedef int VRType;#define INFINITY 10000#define MaxSize 50typedef int PathMatrixMaxSizeMaxSize;typedef int ShortPathLengthMaxSize;typedef int PathMatrixMaxSizeMaxSize;typedef int ShortPathLengthMaxSize;typedef structVRType adj;InfoPtr *info;ArcNode,AdjMatrixMaxSizeMaxSize;typedef structVertexType vexMaxSize;AdjMatrix arc;int vexnum,arcnum;MGraph;typedef structint row;int col;int weight;GNode;void CreateGraph(MGraph *N,GNode *value,int vnum,int arcnum,VertexType *ch)int i,j,k;N-vexnum=vnum;N-arcnum=arcnum;for(i=0;ivexi,chi);for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)N-arcij.adj=INFINITY;N-=NULL;for(k=0;karcij.adj=valuek.weight;void DisplayGraph(MGraph N)int i,j;printf(有向网具有%d个顶点%d条弧,顶点依次是:,N.vexnum,N.arcnum);for(i=0;iN.vexnum;+i)printf(%s ,N.vexi);printf(n有向网N的:n);printf(序号i=);for(i=0;iN.vexnum;i+)printf(%8d,i);printf(n);for(i=0;iN.vexnum;i+)printf(%8d,i);for(j=0;jN.vexnum;j+)printf(%8d,N.arcij.adj);printf(n);void Dijkstra(MGraph N,int v0,PathMatrix path,ShortPathLength dist)int v,w,i,k,min;int finalMaxSize;for(v=0;vN.vexnum;v+)finalv=0;distv=N.arcv0v.adj;for(w=0;wN.vexnum;w+)pathvw=0;if(distvINFINITY)pathvv0=1;pathvv=1;distv0=0;finalv0=1;for(i=1;iN.vexnum;i+)min=INFINITY;for(w=0;wN.vexnum;w+)if(!finalw&distwmin)v=w;min=distw;finalv=1;for(w=0;wN.vexnum;w+)if(!finalw&minINFINITY&N.arcvw.adjINFINITY&(min+N.arcvw.adjdistw)distw=min+N.arcvw.adj;for(k=0;kN.vexnum;k+)pathwk=pathvk;pathww=1;void main()int i,vnum=6,arcnum=9;MGraph N;GNode value=0,1,30,0,2,60,0,4,150,0,5,40,1,2,40,1,3,100,2,3,50,3,4,30,4,5,10;VertexType ch=v0,v1,v2,v3,v4,v5;PathMatrix path;ShortPathLength dist;CreateGraph(&N,value,vnum,arcnum,ch);DisplayGraph(N);Dijkstra(N,0,path,dist);for(i=0;iN.vexnum;i+)if(i!=0)printf(%s-%s:%