用C语言编程实现最短路径道客巴巴

用C语言编程实现最短路径摘 要：最短路径问题研究的问题主要有：单源最短路径问题、与所有顶点对之间 的最短路径问题。在我们的生产生活中遇到最短路径的问题实在太多了，比如乘汽车旅 行的人总希望找出到目的地尽可能的短的行程。如果有一张地图并在图上标出每对十字 路口之间的距离，如何找出这一最短行程？我们首先应该建立它的数学模型，借助图、 矩阵等数学工具，然后根据数学模型写出的算法及其源程序。关键词：C语言，编程，最短路径中图分类号：G343Programs the realization most short-path wages hibiscuswith 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 shortpalh 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 shortpalh Chinese Libraryclassification 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为边上的权集，边上标注的数字表示边的大小，边的大小表示费用；箭头指向的 结点为终止结点，没有箭头的边表示这两站之间相互通车，费用相同。邻接矩阵是表示顶点之间相邻关系的矩阵，设G=(V,E)是具有n个顶点的图，则G的领v83v9接矩阵是具有如下性质的n阶方阵:A= (ajj) nXn其中ajj=O,若从Vj到vj无边相连；ajj=w,若从Vj到Vj有边相连且此边的权为w；矩阵的列表示的是起始结点；行表示的是终止结点；两结点间如果相通，数字表示两结点间边的大小，如果不相通，就没有边的大小，用“0”农示。0 2 0 20 0 0 0A= 0 0 0 60 0 0 0000001000000000010000043061002000000420003000003. 2. 3矩阵的运算及其意义表示两结点之间长度为n的通路，这里的长度是指两结点之间边的数目。所以我们 要计算出An (n的取值为结点的个数)。_063100000_06310000000001000000001000002020000002020000000000100000000010000000604306X00060430600001002000000100200()00000004000000004000020003000020003000000000_000000000_在求出A*1后我们就可求出可达性矩阵，Rn=A+A2+A3+.+An一个图G的可达性矩阵给出了图中各结点间是否可达以及图中是否有回路。4 c语言编程实现4. 1算法的基本思想(数组实现)4.1.1基本思想Dijkstra算法的基本思想是从从vs出发，逐步地向外探寻最短路。执行过程中，与每 个点对应，记录下一个数(称为这个点的标号)，它或者表示从vs到该点的最短路的权(称为 P标号)、或者是从VS到该点的最短路的权的上界(称为T标号)，方法的每一步是去修改T 标号，并且把某一个具T标号的改变为具P标号的点，从而使G中具P标号的顶点数多一 个，这样至多经过nl(n为图G的顶点数)步，就可以求出从vs到各点的最短路。在叙述Dijkstra方法的具体步骤之前，以例1为例说明一下这个方法的基本思想。例 1中，s=lo因为所有Wij0,故有d(vlz vl)=Oo这时，vl是具P标号的点。现在考 察从vl发出的三条弧,(vl, v2)z (vlz v3)和(vl, v4)。如果某人从vl出发沿(vl, v2) 到达v2,这时需要d(vlz vl)+wl2=6单位的费用；如果他从vl出发沿(vl, v3)到达 v3,这时需要d(vlz vl)+wl3 = 3单位的费用；类似地，若沿(vl, v4)到达v4,这时需 要 d(vlz vl)+wl4=l 单位的费用。因为 min d(vlz vl)+wl2,d(vlz vl)+wl3,d(vlz vl)+wl4= d(vl, vl)+wl4=l,可以断言，他从vl到v4所需要的最小费用必定是1 单位，即从vl到v4的最短路是(vl, v4), d(vlz v4) = lo这是因为从vl到v4的任一 条路P,如果不是(vlzv4),则必是先从vl沿(vl,v2)到达v2,或者沿(vl,v3)到达v3。 但如上所说，这吋他已需要6单位或3单位的费用，不管他如何再从v2或从v3到达V4, 所需要的总费用都不会比1小(因为所有wij0)o W而推知d(vl, v4) = l,这样就可以使 v4变成具P标号的点。现在考察从vl及v4指向其余点的弧，由上已知，从vl岀发，分别沿(vl, v2). (vlzv3)到达v2, v3,需要的费用分别为6与3,而从v4出发沿(v4, v6) 到达 v6 所需的费用是 d(vlz v4)+w46=l + 10=ll 单位。因 min d(vlz vl)+wl2, d(vl, vl)+wl3, d(vl, v4)+w46= d(vlz vl)+wl3 = 3o 基于同样的理由可以断言, 从vl到v3的最短路是(vl, v3), d(vl, v3) = 3o这样又可以使点v3变成具P标号的点, 如此重复这个过程，可以求出从vl到任一点的最短路。在下述的Dijstra方法具体步骤中，用P, T分别表示某个点的P标号、T标号，si表示第i步时，具P标号点的集合。为了在求岀从vs到各点的距离的同时，也求岀从Vs到 各点的最短路，给每个点v以一个入值，算法终止时A(v) = m,表示在Vs到v的最短路上，v的前一个点是Vm；如果入(v) = 8,表示图G中不含从Vs到v的路；入(Vs) = O。Dijstra方法的具体步骤：初始化i=0SO=Vs, P(Vs) = O A(Vs) = O对每一个 voVs,令 T(v) = +8, A(v) = + oo, k=s开始 如果Si=V,算法终止,这时,每个veSi, d(Vszv)=P(v)；否则转入 考察每个使(Vk,vj)eE且vj Si的点vj0如果 T(vj)P(vk)+wkj,则把 T(vj)修改为 P(vk)+wkj,把入(vj)修改为 k。) 500)this. resized=true;this.style.width = 500;align = middle ,贝9 把 500)thisresized=tTue;thissHc 宀一匚 align=middle 的 标 号 变 为 P 标 号 卩叫)叫)匚am“心 ed=true;this.style.width = 500;Halign = middle , 令Sixl = Si u (v,.)1几500)this. resized=true;this.style.width = 500;align = middle , k=ii, i=i+l,转，否则终止,这时对每一个 veSi, d(vs,v) = P(v), 而对每一个$(匕v) - T(y) 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;有向图邻接矩阵Varw :GraphType; 图G结构，WI, j表示顶点i到j之间的费用s, n, :integer; s为源点，n为图G的顶点数存放从源点到任意顶点之间的最短路径长度或其上界D:array1MaxNofinteger;SS:array1.MaxNofboolean;标有 P标号的顶点集合pi存放最短路中顶点i的前面顶点编号p:array1.MaxNofinteger;Procedure Init;Var f :text;x, y, nw, I, j: integer;beginassign(f, miniroadroad in);reset(f);readln(f, n, s, nw);for i:=1 to n dofor j:= 1 to n do500) thisresized二true;this, style.width=500; resized二true wi,j:=Maxinit;for i:=1 to nw doreadln(f, x, y, wx, y);close(f);end;Procedure Di jkstra; Di jkstra 算法过程var min, k, i, j, tempk:integer;beginfillchar(SS, sizeof(SS), 0);* 初始化* jSSs :=true;ps :=0; 源点标上 p 标号for i:=1 to n doif iOs then Di:二ws, i;Ds:=0;k:=s;min:二T;While minOMaxint do 当存在所有T标号点的距离上界的最小值Beginmin:= Maxint;for j:=l to n do begin 在所有T标号点进行操作500) this# resizcd=true;this stylc. width=500; 如果j未标p标号，且到j的路径长度上界可更新，则更新为最小值if (not ssj)and(wk, jOMaxint)and(djDk+wk, j) then beginDj:= Dk+wk, j;Dj:二k;end;end;if n)in4. 2算法对应的源程序# i nclude# i nelude /Di jkstra算法实现函数void Dijkstradnt 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卄)dist i = costv i;si = 0;if (disti = maxint)previ = 0;elseprevi = v;distv = 0;sv = 1;/源节点作为最初的s子集for (i = 1; i n; i卄)fint 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 (!sjj) & (costuj maxint) int newdist = distu + costuj; if (newdist = 1; j-)printf (，z%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&n);printf(please input the cost status:n);cost=(int. *)malloc(sizeof (int)*(n+1);for (i = 1; i = n; i+)costi = (int *)malloc(sizeof(int)*(n+1);/输入代价矩阵for (j = 1; j = n; j+)for (t = 1; t 二 n; t+)scanf&costj t);dist = (int *)malloc(sizcof(int)*n);prev = (int *)malloc(sizeof(int)*n); printf(please input the source node:);scanf&v);/调用di jkstra算法Di jkstra(n, v, dist, prev, cost);printf (have confirm the best pathn);printf(*n); for(i = 1; i 3thedistance cost fvon node 2tonode4is2thepi*e-node of node 4 is node2thebest path is:2 4thedistance cost fron node 2tonode5is3thepre-node of node 5 is node4thebest path is:2 -： 4 - 5thedistance cost from node 2tonode6is5thepre-node of node 6 is node5the best path is:2 - 4 - 5 - 6Pfgss any key to continue5结束语参考文献1徐洁磐.离散数学导论一3版.北京:髙等教育岀版社,2004.62谢永钦试论信息与计算机科学专业的改革与发展J数学理论与应用，2002,22(4):45)6同济大学应用数学系.丁程数学线性代数.北京:高等教育出版社.http:/www.hep.edu.en/.2003.74陇东学院教务处教学计划ZJ.200L12