用C语言编程实现最短路径.doc

用C语言编程实现最短路径 摘 要: 最短路径问题研究的问题主要有：单源最短路径问题、与所有顶点对之间的最短路径问题。在我们的生产生活中遇到最短路径的问题实在太多了，比如乘汽车旅行的人总希望找出到目的地尽可能的短的行程。如果有一张地图并在图上标出每对十字路口之间的距离，如何找出这一最短行程？我们首先应该建立它的数学模型，借助图、矩阵等数学工具，然后根据数学模型写出的算法及其源程序。关键词：C语言，编程，最短路径中图分类号：G343Programs the realization most short-path wages hibiscus with the C languageXinjinrong (east Gansu institute computer and the information science institute 2007 level of 4 class of Gansu Qingyang 745000) the abstract: The most short-path question research question mainly has: Simple source most short-path question, and all apexes to between most short-path question.Met the most short-path in ours production life the question too to be really many, for instance rode the automobile travel the human always hoped discovered to destination as far as possible short traveling schedule.If has a map and leaves in the chart superscript every time to between the intersection distance, how discovers this shortest traveling schedule? We first should establish its mathematical model, with the aid of mathematical instruments and so on the chart, matrix, then the algorithm and the source program which writesaccording to the mathematical model. Key word: C language, programming, most short-path Chinese Library classification number: G3431最短路径及其相关概念最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两节点之间的最短路径。算法具体的形式包括：（1）确定起点的最短路径问题即已知起始结点，求最短路径问题。（2）确定终点的最短路径问题与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，再有向图中该问题等同于把所有路径方向反转的确定起点的问题。（3）确定起点终点的最短路径问题即已知起点和终点，求两结点之间的最短路径。最短路径问题研究的问题主要有：单源最短路径问题、与所有顶点对之间的最短路径问题。1.1最短路径的基本概念1.2与其相关的概念为了更好理解什么是最短路径，首先我们就该清楚以下的问题。（1）通路：在一序列中，中间每个结点均与其前、后结点相邻接，这种边的序列称为图的通路。通路中边的数目称为通路的长度。（2）回路：图中一条通路如果起始结点与终止结点相同，则称此通路为回路。（3）简单路径：有向图中各边全不同的通路称为简单路径。（4）基本路径：有向图中各点全不同的通路称为基本路径。2最短路径的意义及其在现实生产生活中的应用在我们的生产生活中遇到最短路径的问题实在太多了，比如乘汽车旅行的人总希望找出到目的地尽可能的短的行程。如果有一张地图并在图上标出每对十字路口之间的距离，如何找出这一最短行程？一种可能的方法就是枚举出所有路径，并计算出每条路径的长度，然后选择最短的一条。我们很容易看到，即使不考虑包含回路的路径，依然存在数以万计的行车路线，而其中绝大多数是不值得考虑的。我们将阐明如何有效地解决这类问题。在最短路径问题中，我们如何将文字叙述转换为数学模型呢？3最短路径的数学模型实现3.1数学模型数学模型是人们为了了解周围的世界，把自己的观察及思想组织成概念体系。我们把这些概念体系称为模型。把逻辑应用与模型的概念而得到的见解称为理论。数学模型是各种模型中最严密的模型。其正确性是通过逻辑和实践来检验。20世纪数学模型有了很大的发展。其原因有三：一，数学理论的系统化，二，计算机的诞生，三，应用数学的大发展。数学就是一个对未来作出预见的重要工具，它常常能以足够的精确度对未来作出预见，告诉我们未来的发展趋势。数学模型就像一张指示方向的交通图，也像建筑的设计图，虽然简单却切中要害。数学模型在各方面影响着我们。从大的方面讲，财政预算，人口控制；从个人角度讲，以购房为例，除去交预付款外，还要每月扣除。这都需要数学模型的帮助。数学模型可以分为连续型模型、离散型模型、随机型模型等。数学模型建立一般分为五个阶段：（1）科学地识别与剖析实际问题；（2）形成数学模型；（3）求解数学问题；（4）研究算法，并尽量使用计算机；（5）回到实际中去，解释结果。最短路径的实现必须借助图、矩阵等数学工具。3.2具体实现举例已知某人有一张A城市的内部交通图，公交车从第一站出发可以到第二站、第三站及第四站，它们的费用分别是6元、3元和1元；从第二站可以到第五站，费用为1元；从第三站可以到第二站和第四站，费用都为2元；从第四站可以到第六站，费用为10元；从第五站可以到第六站、第七站及第八站，费用分别为4元、3元和6元；从第六站可以到第五站和第七站，费用分别为10元和2元；从第七站可以到第九站，费用为4元从第八站可以到第五站和第九站，费用分别为2元和3元；某人想从第一站到第八站去，求使总费用最小的旅行路线。3.2.1实例转换为有向图下图为上述文字转换的有向加权图G=（V,E,W）,其中V为顶点集，Vn表示每一站，有多少站就有多少个结点，n可以取1，2，3，n；E为有向边集，有边表示两站之间是相通的；W为边上的权集，边上标注的数字表示边的大小，边的大小表示费用；箭头指向的结点为终止结点，没有箭头的边表示这两站之间相互通车，费用相同。3.2.2用邻接矩阵表示有向图G邻接矩阵是表示顶点之间相邻关系的矩阵，设G=(V,E)是具有n个顶点的图，则G的领接矩阵是具有如下性质的n阶方阵：A=（aij）nn其中aij=0，若从vi到vj无边相连；aij=w，若从vi到vj有边相连且此边的权为w；矩阵的列表示的是起始结点；行表示的是终止结点；两结点间如果相通，数字表示两结点间边的大小，如果不相通，就没有边的大小，用“0”表示。A=3.2.3矩阵的运算及其意义An表示两结点之间长度为n的通路，这里的长度是指两结点之间边的数目。所以我们要计算出An（n的取值为结点的个数）。A2=在求出An后我们就可求出可达性矩阵，Rn=A+A2+A3+An一个图G的可达性矩阵给出了图中各结点间是否可达以及图中是否有回路。4 c语言编程实现4.1算法的基本思想 (数组实现)4.1.1基本思想Dijkstra 算法的基本思想是从从vs出发，逐步地向外探寻最短路。执行过程中，与每个点对应，记录下一个数(称为这个点的标号)，它或者表示从vs到该点的最短路的权(称为P标号)、或者是从vs到该点的最短路的权的上界(称为T标号)，方法的每一步是去修改T标号，并且把某一个具T标号的改变为具P标号的点，从而使G中具P标号的顶点数多一个，这样至多经过n-1(n为图G的顶点数)步，就可以求出从vs到各点的最短路。在叙述Dijkstra方法的具体步骤之前，以例1为例说明一下这个方法的基本思想。例1中，s=1。因为所有Wij0，故有d(v1, v1)=0。这时，v1是具P标号的点。现在考察从v1发出的三条弧，(v1, v2), (v1, v3)和(v1, v4)。如果某人从v1出发沿(v1, v2)到达v2，这时需要d(v1, v1)+w12=6单位的费用；如果他从v1出发沿(v1, v3)到达v3，这时需要d(v1, v1)+w13=3单位的费用；类似地，若沿(v1, v4)到达v4，这时需要d(v1, v1)+w14=1单位的费用。因为min d(v1, v1)+w12，d(v1, v1)+w13，d(v1, v1)+w14= d(v1, v1)+w14=1，可以断言，他从v1到v4所需要的最小费用必定是1单位，即从v1到v4的最短路是(v1, v4)，d(v1, v4)=1。这是因为从v1到v4的任一条路P，如果不是(v1, v4)，则必是先从v1沿(v1, v2)到达v2，或者沿(v1, v3)到达v3。但如上所说，这时他已需要6单位或3单位的费用 ，不管他如何再从v2或从v3到达v4，所需要的总费用都不会比1小(因为所有wij0)。因而推知d(v1, v4)=1，这样就可以使v4变成具P标号的点。现在考察从v1及v4指向其余点的弧，由上已知，从v1出发，分别沿(v1, v2)、(v1, v3)到达v2, v3，需要的费用分别为6与3，而从v4出发沿(v4, v6)到达v6所需的费用是d(v1, v4)+w46=1+10=11单位。因min d(v1, v1)+w12，d(v1, v1)+w13，d(v1, v4)+w46= d(v1, v1)+w13=3。基于同样的理由可以断言，从v1到v3的最短路是(v1, v3)，d(v1, v3)=3。这样又可以使点v3变成具P标号的点，如此重复这个过程，可以求出从v1到任一点的最短路。在下述的Dijstra方法具体步骤中，用P，T分别表示某个点的P标号、T标号，si表示第i步时，具P标号点的集合。为了在求出从vs到各点的距离的同时，也求出从Vs到各点的最短路，给每个点v以一个值，算法终止时(v)=m，表示在Vs到v的最短路上，v的前一个点是Vm；如果(v)=，表示图G中不含从Vs到v的路；(Vs)=0。Dijstra方法的具体步骤：初始化i=0S0=Vs，P(Vs)=0 (Vs)=0对每一个vVs，令T(v)=+ ，(v)=+ ，k=s开始如果Si=V，算法终止，这时，每个vSi，d(Vs,v)=P(v)；否则转入 考察每个使(Vk,vj)E且vj Si的点vj。如果T(vj)P(vk)+wkj，则把T(vj)修改为P(vk)+wkj，把(vj)修改为k。令500)this.resized=true;this.style.width=500; align=middle 如果500)this.resized=true;this.style.width=500; align=middle，则把500)this.resized=true;this.style.width=500; align=middle的标号变为P标号500)this.resized=true;this.style.width=500; align=middle，令500)this.resized=true;this.style.width=500; align=middle ，k=ji，i=i+1，转，否则终止，这时对每一个vSi，d(vs,v)=P(v)，而对每一个500)this.resized=true;this.style.width=500; align=middle 。4.1.2算法的描叙过程Program Min_Road_Dijkstra;Const MaxN=100;Type GraphType=Array1. MaxN, 1. MaxN,of integer; 有向图邻接矩阵Var W : GraphType; 图G结构，WI,j表示顶点i到j之间的费用 s,n, : integer; s为源点，n为图G的顶点数 存放从源点到任意顶点之间的最短路径长度或其上界 D : array1. MaxN of integer; SS : array1. MaxN of boolean; 标有P标号的顶点集合 pi存放最短路中顶点i的前面顶点编号 p ： array1. MaxN of integer;Procedure Init; Var f :text;x,y,nw,I,j:integer;begin assign(f,miniroadroad.in); reset(f); readln(f,n,s,nw); for i:=1 to n dofor j:= 1 to n do 500)this.resized=true;this.style.width=500;“resized=true” wi,j:=Maxinit; for i:=1 to nw do readln(f,x,y,wx,y); close(f);end;Procedure Dijkstra; Dijkstra算法过程var min,k,i,j,tempk:integer;begin fillchar(SS,sizeof(SS),0); *初始化* SSs:=true;ps:=0;源点标上p标号 for i:=1 to n do if is then Di:=ws,i; Ds:=0; k:=s; min:=-1; * While minMaxint do 当存在所有T标号点的距离上界的最小值 Begin min:= Maxint; for j:=1 to n do begin 在所有T标号点进行操作 500)this.resized=true;this.style.width=500; 如果j未标p标号，且到j的路径长度上界可更新，则更新为最小值 if (not ssj)and(wk,jMaxint)and(djDk+wk,j) then begin Dj:= Dk+wk,j; Dj:=k; end; end; if min4.2算法对应的源程序i ncludei nclude /Dijkstra算法实现函数void Dijkstra(int n,int v,int dist,int prev,int *cost)int i;int j; int maxint = 65535;/定义一个最大的数值，作为不相连的两个节点的代价权值 int *s ;/定义具有最短路径的节点子集ss = (int *)malloc(sizeof(int) * n); /初始化最小路径代价和前一跳节点值 for (i = 1; i = n; i+) disti = costvi; si = 0; if (disti = maxint) previ = 0; else previ = v; distv = 0; sv = 1;/源节点作为最初的s子集for (i = 1; i n; i+) int temp = maxint; int u = v; /加入具有最小代价的邻居节点到s子集 for (j = 1; j = n; j+) if (!sj) & (distj temp) u = j; temp = distj; su = 1; /计算加入新的节点后，更新路径使得其产生代价最短 for (j = 1; j = n; j+) if (!sj) & (costuj maxint) int newdist = distu + costuj; if (newdist = 1; j-)printf(%d - ,wayj);printf(%dn,u);/主函数，主要做输入输出工作void main()int i,j,t;int n,v,u;int *cost;/代价矩阵int *dist;/最短路径代价int *prev;/前一跳节点空间printf(please input the node number: );scanf(%d,&n); printf(please input the cost status:n);cost=