数学建模-无向图最短路径

1、参赛队编号：244赛题类型代码：b无向图最优路径摘要：在实际生活中，我们经常会遇到“最优路径”问题，例如，城市之间的最短线路，或者城市之间最节省的交通费用等问题都属于该类问题。同样，在自然界也存在着“最优路径”。在复杂多变的蚁巢中，蚂蚁总是能以最快、最高效的方式游历在各个储藏间，今天，蚁后让小蚁同学按照自己特定的要求寻找食物，针对蚁后的要求，我们采用了大量科学分析方法，并进行了反复验证，我们建立如下的模型：首先对问题进行分析，对约束条件逐一列举、分析实质，必须经过N7、N12两个点，必须经过两条直线，实质是经过四个点N2、N4、N13、N14，但这四个点又与前边两个点有所不同，N2和N4要相邻

2、，N13和N14要相邻，必须经过起始和终止点（针对此处的歧义，在假设中解决）深入分析可知，若最多经过9个点是无法完成的，因此求次优解。其次遍历所有路径找到符合约束条件的，遍历时使用穷举法，走遍每一条可以走的路，在过走点数超过限制的最多点数或者已经走到了终点，是，则停止，判断这条是否满足约束条件，满足则记录这条路的信息，不满足什么都不做；否，则继续向前走。最后可以找到所有经过不超过限制点数、满足约束条件的路径。再计算每一条符合要求的费用（事实上可以集成到上一步中，但为了模块独立化，利用分而治之思想，在这里将其分开），按照费用排序，在所走点数的基础上，在费用上再做分析，选出最优路径。最后对模型进行

3、分析与评价，以及改进与退关，模型的适用性较强，只要对数据稍加改动就可以成为求有向图最佳路径的模型。关键字：无向图最优路径，C语言，图论，算法目录TOC o 1-5 h z HYPERLINK l bookmark4 o Current Document 一、问题重述1 HYPERLINK l bookmark6 o Current Document 二、模型假设与符号说明22.1模型假设22.2符号说明2 HYPERLINK l bookmark8 o Current Document 三、问题分析23.1整体分析23.2约束条件分析23.3可行性分析2 HYPERLINK l bookmar

4、k10 o Current Document 四、模型建立与求解34.1模型准备34.2模型建立与求解34.2.1确定所有路线表达式3对路径的筛选44.2.3费用分析54.2.4算法设计64.2.5模型求解74.3对模型的检验7 HYPERLINK l bookmark12 o Current Document 五、模型评价95.1模型优缺点95.1.1模型优点105.1.2模型缺点105.2模型改进10 HYPERLINK l bookmark14 o Current Document 参考文献10附录11 无向图最优路径模型一、问题重述最强大脑中的收官蜂巢迷宫变态级挑战，相信大家都叹为观止

5、！最强大脑收官战打响后，收视率节节攀升，就连蚁后也不时出题难为一下她的子民们。在动物世界中，称得上活地图的，除了蜜蜂，蚂蚁当仁不让。在复杂多变的蚁巢中，蚂蚁总是能以最快、最高效的方式游历在各个储藏间（存储食物）。今天，她看完最新一期节目，又发布了一项新任务：小蚁同学，我需要玉米库的玉米，再要配点水果，去帮我找来吧。小蚁正准备出发，蚁后又说：哎呀，回来，我还没说完呢，还有若干要求如下：小蚁同学，你需要尽可能以最少的花费拿到食物（附件图中路线上的数值表示每两个储物间的花费）；小蚁同学，你最多只能经过9个储藏间拿到食物（包含起止两个节点，多次通过同一节点按重复次数计算）；小蚁同学，你必须经过玉米间，

6、水果间（附件图中标绿色节点）；别忘了，食蚁兽也在路上活动呢，一旦与食蚁兽相遇，性命危矣！不过小蚁微信群公告已经公布了敌人信息（附件图中标红色路段）；最后，千万别忘了，还有两段路是必须经过的，那里有我准备的神秘礼物等着你呢（附件图中标绿色路段）。这下小蚁犯难了，这和它们平时找食物的集体活动规则不一样嘛,看来这次需要单独行动了。要怎么选路呢？小蚁经过一番苦思冥想，稿纸堆了一摞，啊，终于找到了！亲爱的同学们，你们能否也设计一种通用的路径搜索算法，来应对各种搜索限制条件，找到一条最优路径，顺利完成蚁后布置的任务呢？注：1、蚁巢，有若干个储藏间（附件图中圆圈表示），储藏间之间有诸多路可以到达（各储藏间拓

7、扑图见附件）;2、节点本身通行无花费；3、该图为无向图，可以正反两方向通行，两方向都会计费，并且花费相同；4、起止节点分别为附件图中S点和E点。二、模型假设与符号说明2.1模型假设1因为题目中并未明确给出是否是从起始点开始到达终止点，即从S到e,为防止歧义、方便计算，假设每条路径都是从起点到终点；2.下文中说到的点或点数均代表存储室或存储室数量；3通过图1各路段关系，可以假设，为得到最优路径，不会再从N1、N2、N3走回起点。2.2符号说明符号含义N最多经过的点的个数Xn经过的第n个点Pi第j个集合耳个点中的第i的数值，即将要走向的下一个点PiiP.J第j个点所有与其相邻的点的集合APC,k和

8、第k个点相邻的点的总数J走过的第k个点集合兀素的下标，从0至【APC.-1走第k条路所需要的总费用从编号为i的点到编号为j的点的费用，即表3i行j列对应的值表1三、问题分析整体分析题目的总体思路是在各种约束条件下求出一条从起点到终点的最优路径，最优可以说是有两个方面：第一是经过的储藏室即经过的点最好，题目中给定为9个，第二是在途中花费的费用最少。基于以上分析，我们决定建立无向图最优路径模型，从通过的点数和费用进行优化。约束条件分析题目中并未明确给出是从起始点到达终点(即图中给出的s和e),为了不产生歧义，以及方便计算，我们在假设中规定该路线是从起始点到达终点(即图1中给出的s和e)。最多只能经

9、过9个储藏室(即9个点)必须经过两条绿色的路线，即必须经过N2、N4、N13、N14，并且N2和N3相邻，N13和N14相邻。必须经过水果间和玉米间，即必须经过N7和N12。不能经过有食蚁兽的红色路段，可以有两种解决办法，第一：即N11和N12不能相邻出现，第二：Nil和N12之间没有连线，没有通路。所有的路都是可以双向通行的。可行性分析经过约束条件的分析，我们发现，有八个特殊点(N2、N4、N7、N12、N13、N14、）必须经过，那么按照题目要求，只能再选择一个非特殊点通过以完成该路径，通过图1分析，这显然是无法完成的，经过进一步的分析与计算，我们发现在满足以上约束条件的情况下，最少需要通

10、过11个点才能完成任务（相关计算与证明在4.3.1中给出）。四、模型建立与求解4.1模型准备影响实际问题的因素很多，要解决实际问题就要建立适当的模型，既要把所得模型的次要因素忽略，否则所得模型会因为结构复杂而失去可解性同时又不能把与实质相关的因素忽略掉，而造成所得模型不能够正确反映实际情况而失去可靠性。但若是无法取得实际问题的最优解，只能在牺牲次要因素的条件下获得最优近似解。因此要对实际问题进行简化、确定变量和参数，并用某些“规律”建起变量与参数间的数学模型。影响路线选择因素很多：经过储藏间数量限制、必经节点与路径、危险路径阻碍、费用最少。对于问题中两种不同决策变量最少节点与最少花费建立两种模

11、型分别求出在侧重点不同情况下的最优解。经过以上的问题分析，针对此问题应该建立一个无线图最优路径模型。模型的建立与求解此模型是要找出从起始点到终点满足约束条件，并且使得经过的点最少、费用最少，因此其核心表达式是一个由一个点指向另一个点的路线。T%N1iXN2N1式（1）式（2）4.2.1确定所有路线表达式TXTXT%TOC o 1-5 h z23N2TPitPit-piTp心L1?L2xM3匚N2乂i60,APC21T公式说明：式（1）表示从到xN1的所有点，用有向箭头连起来，表示一条经过了N的点的路径，起始点显而易见为%o，终点为xN1。式（2）与式（1）对应，P.i对应%n，Pi为x“的确定

12、方法。比如此时走到尤2点，那么下一个点的确定必然与勺有关，具体由笃集合中的第i（i从0到apc2-1）个元素确定。第j个点的编号即对应的j、APCj、Pj都在表2中有详细列举。公式意义：从开始，遍历与它相邻的所有点，并且每个点都尝试走，走到下一个点，同样遍历与其相邻的所有点,重复上述步骤，直到走到第N个点（即编号为N-1的点），便不再继续走，或者没有走到第N个点，而是已经走到了终点即e，也不再继续走。这样可以找到所有走过点数为N或者能到达终点的路径。点编号对应符号与其相邻点的总数列举相邻的点01234560Po31231Pi32492笃413453卩3425674P4412595P572346

13、910126P6735781213147P733688P846714159P95145101110P10459111211Pi139101612Pi255610131613Pi366121415161714Pi4468131515P154813141716Pi641112131717Pi700表2各节点信息表对路径的筛选（添加程序）（1）限制经过的最多点数为了保证程序能够正常、快速地运行，在第一步寻找路径中其实已经限制了最多经过的点数，走到第N个点（即编号为N-1的点），便不再继续走，或者没有走到第N个点，而是已经走到了终点即e,也不再继续走，这样已经保证了每条路走过的点数都限制在N个以内。（

14、2）经过N7和N12每条路走完之后，遍历一下所有的点，看看其中是否有7和12这两个值，没有的话此路不满足约束条件，否则继续检验其他条件。（3）经过两条绿的路线首先可以确定2、4、13、14必须通过，就是必须有这两个数值，其次，2和4,13和14还必须相邻出现，才能说明通过绿的路段。（4）不经过红的的路线，两种解决方案第一：直接切断Nil和N12间的路线，在表2中编号为11的节点中不添加12这个相邻节点，在编号为12的节点中不添加11这个相邻节点，这样所得到的路线绝对不会经过红色路段。第二：每条路走完之后，遍历一下所有的点，寻找N12与N13是否相邻出现过，若出现过，这说明经过了红色路段，否则，

15、未经过，符合约束条件，继续检验其他条件。注：本算法用第一种解决方案实现！费用分析经过上述分析与计算，已经求得了满足所有约束条件并且经过的点尽量少的路径，接下来还需要考虑每条路径的费用。(1)费用计算X0X1X2X3XN2Si式(3)式(4)设有一条符合条件的路径如下其费用F.=f+f+f+f+f:尢0尢1尢1尢2尢2尢3尢N3尢N2儿N2兀N1(2)费用排序将所得到的路径按照计算的费用升序排序，每条路的费用将会一目了然，结合通过的点数、费用选取最优路径。占八、编号012345678910111213141516170031100000100000000130101000000000000021

16、101210000000000003101002210000000000401210100010000000050012001003103000006000201012000243000700010010100000000080000002100000013009040013000011000000100000010001012000001100000000011010001012000003200021020010130000004000002012211400000030100001010015000000003000021004160000000000011120011700000000

17、0000010410表3费用表算法设计核心代码如下：voidfindMoreShortPath(intindex,int*pointCount)inti;将第一个点编号写入路径信息实例*(allPathpathNum.pathPoint+(*pointCount)-1)=index;如果已经到最后一个点或者走过的点数超过POINT_COUNT_MAX,对此路径进行处理if(*pointCount=POINT_COUNT_MAX|index=ENDNDEX)如果此时最后一个点的编号为最后一个点的，那么继续对此路径进行处理if(index=END_INDEX)判断此路径是否满足约束条件，是则继续i

18、f(checkPointOfPath()给pathNum先加一，以防止覆盖上一条符合条件的路径pathNum+;因为不会再从头开始遍历，下一条路的前半部分与上一条路是相同的因此将上一条路径的信息赋给下一条路径，分叉之后的路径会在上边被修改for(i=0;iPOINT_COUNT_MAX;i+)*(allPathpathNum.pathPoint+i)=*(allPathpathNum-1.pathPoint+i);else如果不满足以上条件，继续向前走for(i=0;i2-4-5-12-6-7-8-14-13-e式（5）s-2-4-5-12-6-7-6-14-13-e式（6）2、费用最少的路径

19、有两条，第一条经过12个点，第二条经过13个点，费用都为13，路径如下：s-2-4-5-6-7-8-14-13-12-16-e式（7）s-2-5-4-2-3-7-8-14-13-12-16-e式（8）4.3对模型的检验1.将N置为9或10时，程序运行结果如下：C；U5er1Ja37lD&=kttpVESt22_2-X0r7FFB31D670E3ANOMALY,useofREX.wiwmeaningIess（defau11operandizei564）卜未找到得舍的路径i|图3当设置N为9或10时均未找到符合条件的路径，说明经过最少点数为9或10时均无法完成此任务，而设置为11及以更多时，会找到

20、符合条件的路径。这些检验结果验证了3.3可行性分析的正确性，按照原题约束条件，此题无解。2.将N置为11时，程序运行结果如下：is64)TOC o 1-5 h zCU-5er5108370ieslttoptff5B22_2.rxeL0 x7FFB3W670E?ON0MALY:useofREX.wismeaningIessoperandwize第1条路线：0-2-4-5-1-6-7-8-14-13-17忌费用7?：14第2条路钱0-24-5-12-6-7-6-14-13-17总费用为i厲图4所以得出节点最少的路径有两条，费用分别为14和16：分别是s-2-4-5-12-6-7-8-14-13-e

21、式（9）s-2-4-5-12-6-7-6-14-13-e式（10）将N置为12时，程序运行结果如下:用用用用用用用用用用用用用用用用用用用总总忌总总意总总总意总总总总总总总息总Ox7FFB31D670E3：ANOMALY;useofREX.w1条路线：o-2-45-6-7-o-2-4-5-3-7-o-24-5-6-7-Q-2-4-5-6-7-o-2-4一2-3-7-o-2-4一5-6-1l2-ismeaningIess(defau11operand8-14-13-12-16-17卓费用8-14-13-12-16-17总费用6-12-13-14-13-17总费用0-1413-12-13-17总费

22、用0-14-13-12-16-17总费用6-7-S-14-13-17意费用0-2-4-5-12-6-7-0-14-13-17-17,0-2-4-9-10-12-6-7-8-14-13-171。条路线11条路线12条路线13条路线14条路贱15条路蝮2条路线17条路线条路线19条路线曲条路线21条路线22条路线23条路蝮24条路线25条路线笳条路线27条路线曲条路线西条路线30条路线引条路线舵条路线33条路钱34条路线M5条路线丝条路线3了条路线38条路线沙築路战4D条路线41条路线0-1-4-2-3-7-8-14-13-12-16-170-2-45-3-占-12-13-114-13-170-2

23、-4-5-7-3-14-13-12-13-170-24-23-7-6-12-13-14-13-170-2-42-3-70-14-13-12-13-170-2-4一5-6-了一&-14一13H2-刿6-1了0-3-2-4-5-12-6-7-8-14-13-170-3-73-2-4-5-12-13-14-13-170-1-4-2-3-7-6-12-13-14-13-170-2-456-126-76-14-13-171-4一2-3-了一8-M4-l31l2-M3-)170-2-4-5-10-12-6-7-r-14-13-170-24-5-6-7-6-12-6-14-13-170-0-0-0-1F70

24、-0-0-0-0-0-0-0-0-0-0-0-0-0-2-4-5-12-52-4-5-12-Z245-12占-2-4-5-12-6-2-4-5-12-6-2-2-5-12-24-5-12-6-2-4-9-10-12-2-4-5-6-7-2-4-2-3-7-2-4-5-3-7-1-4-2-3-7-4-2-5-124-3-了一2-4-5-12-4-5-12-6-2-4-5-3-724?-5-122-4-5-6-7-7-S-14-13-173-7-3-14-13-17石-、已14-苗了6-1413-17-177-S-14-13-16-176-7-8-14-13-170-7-3-14-13-176-7

25、-6-14-13-176-14-13-12-13-17&-14一13-12-16-了6-14-13-12-16-176-14-13-12-16-176-7-8-14-13176-12-irl4-13-177-8-14-13-173-15-14-13-176-12-6-14-13-176-7-3-14-13-176-12-13-14-15-17在i&64)*1314141414141414141515151515151515161616161616161616161616161616161717171717171717图5共找到73条符合条件的路径，其中经过11个点的路径已被标出，费用最少的情况

26、为经过12个点，费用为13，可行路径有一条，为：s-2-4-5-6-7-8-14-13-12-16-e式（11）4.将N置为13时，程序运行结果如下：EC：Ml5ers10BB7Dektoptt2Z2.exeX 线銭线线线线线线线线线线线线线线线线线线线线些1D路路路路路路路路路路路路路路路路路路路路路路路B3弟条条条条条条条条条条条条条条条衆条条条条采卑、A.A、L;4-5-4-4-4-4-4-m4-4-5-54-2-5-4-4-4-MAL-T-T7-T-T-T-T-D22222222222222222233222useofRE冥.wsmeaningIess(defau11operands5

27、-6-7-3-14-13-12-16-17-1723-7-S-M4-13-12-16-179-10-12-6-7-8-14-13-173-7-3-14-13-12-16-17-172-3-7-E-M4-13-12-16-175-3-7-5-14-13-12-16-17-175-6-7-6-12-13-14-13-17-175-6-7-S-14-13-12-13-17-172-3-7-B-M4-13-12-16-176-7-8-14-13-16-12-16-175-6-12-67-8-14-13-17-175-10-12-6-7-3-14-13-17-175-12-6-7-14-13-17-17

28、-179-10-12-6-7-8-14-13-17-179-11-16-12-6-7-8-14-13-174-2-3-7-6-12-13-14一13-174-2-3-7-B-14-13-12-13-171-2-3-7-6-1413-12-16-175-6-7-8-14-13-12-16-174一2-3-7-S-14-13-M216-173-7-3-14-13-16-12-16-175-4-5-12-6-7-6-14-13-175-6-3-7-8-14-13-12-16-17A33444444444444444444555JIJIJI4Ji4J1XIV64Jp勺_21-勺切勺勺切勺勺切勺切勺勺一

29、勺s_djm*nnm*_djm*rrr*m*3Jnrm*m*3Jrrr*rn?m*nrrrr*m*rrr*nr?-1费费贾费费费费费费费费费费费费费费费费费養费费总总总总总总总总总总总总总总总息总总总忌总总总图6共找到1018条符合条件的路径，从结果可以看到，也能找到一条费用最少的路径，为13，路径如下：s-2-5-4-2-3-7-8-14-13-12-16-e式（12）4.将N置为14时，程序运行结果如下：CUstri1M37DesktcptE5f_2sK=OxTFFbSidJtOESoJiOMALY:R僚踣线:第2圣躇裟:第H昙捋塗:第碌路线:筮5冬踣线:第&食路线:第7熹路线:第呂簧踣线

30、:第协食壇线:第1僚路线:第12冬踣线:第13线:第14套路线:第15老蹈线:第也条路這:第口董路钱:第寮路幾:第旳無踣线:第2D鬟瞥线:第21第路线:油射i.0-24-0-2-5-0-2-4-0-2-4-0-2-4-0-2-4-0-2-4-0-240-2-4-0-2-4-0-2-4-0-2-1-0-2-4-0-2-4-0-24-0-2-+-0-2-4-2-4-0-2-5-0-2-5-0-2-1-usecfREX.nismea(defaultoperand5-6-7-0-14-113-12-11-1717-172-3-7-S-14-13-12-?117-?171-2-3-7-8-1413-12

31、-16-17-179-1Q-12-6-7-6-U-13-17-171一9一11一;Td-l27-8-14-13_173-7-8-14-13-12-16-17-17-172-3-7-6-14-13-12-16-17-175-3-7-6-14-113-12-16-17-17-174_5_&7_8_14-13_?12_16-175-6-7-6-12-13-17-17-175-6-7-8-14-13-12-13117-172-3-7-S-14-1312-1617-176-7-8-14-13-1612-16-17-175-6-12-6-7-6-14-13-17-17-175-10-12-6-7B-14t

32、-13-17-17-175-12-6-?-S-14-13-1/-?17-17-?179-10-12-6-7-6-14-13-17-17-179-11-16-1?-6-7-0-14-13-17-174一2-3-/7-6-12-13-M4一13-17-174-2-3-7-B-14-13-12-13-17-179-4-2-3-7-8-14-z13-12-16-17A-、r、M?sizei&64）总段用为1M总实用为：估总姜用为：14总炭用为：14总费用为；14总黃戸：4总贾用为：口总眾用为彳14总费月为：2总费用14总棗用14总费用为；14总费用为=14忌疑月为：M总眾用5*3114思要用为：14总

33、费用.为：14总叛用14总费用为；14总费冃：4总疑用为：14ath田吐.1图7由此运行结果分析可知，经过14个点以及14个点以上，不会再有费用最少的路径。五、模型评价5.1模型优缺点 5.1.1模型优点（1）算法中使用递归进行路径的检索，这样可以大大地提高代码的运行速度，即使数据比较庞大，也能很快求解；（2）此模型看似是针对无向图求解最优路径的模型，实际上针对有向图同样适用，并且计算起来更加快速，如何推广位有向图最优路径的模型在5.2模型改进中讲到；（3）对此网络的规模增大缩小都是适用的，只需要对矩阵进行扩充，填入新增加的数据，修改少量参数；（4）能够列出除最优路径之外的其他很多路径，这为寻

34、找其他合适的路径提供了方便。5.1.2模型缺点（1）暂时所有的数据都是直接从源代码中陆入进去的，这就需要使用此模型的人非常熟悉这个模型才能保证修改后的矩阵和常量不出问题；（2）算法中，对约束条件进过两条绿线的判断比较繁琐，修改时容易出错；（3）模型中加入的影响因比素较少，在投放到实际问题中可能会出比较大的偏差。5.2模型改进此模型此次计算是针对题目中的无向图来设计与填充数据的，但是只要稍加改动，便可以成为几个无向图最优路径算法。以本题目为例，假如只能从N2走到N4,那么要修改的只有两个地方，而且是点的信息矩阵，将N4相邻点的个数减1,相邻点中将2除去，这样便实现的从N2到N4的单方向，其他节点

35、也是相同。完成了对无向图的模型。参考文献姜启源.数学模型.高等教育出版社.2011.ThmoasH.CormenCharlesE.LeisersonRonaldL.RivestCliffordStein著，殷建平徐云，王刚，刘晓光，苏朋，邹恒明，王宏志译.算法导论.机械工业出版社2013.01.附录：源代码如下：#includevstdio.h/最大允许通过的点数#definePOINT_COUNT_MAX14/最后一个点的下标TOC o 1-5 h z#defineEND_INDEX17#defineBooleanint#defineTRUE1#defineFALSE0/节点结构体，包含相邻

36、点的个数adjoinPointCount，以及对应的各个相邻点adjoinPointtypedefstructPOINTintadjoinPointCount;intadjoinPoint20;POINT;/路径结构体，pathPoint用来保存符合条件的路径，以及费用allFaretypedefstructPATHintpathPointPOINT_COUNT_MAX;intallFare;PATH;在遍历路径时，符合条件的路径编号intpathNum=0;保存所有的符合条件的路径信息PATHallPath1000000;/点信息矩阵POINTconstpoint18=/*0*/3,1,2,

37、3,/*1*/3,2,4,9,/*2*/4,1,3,4,5,/*3*/4,2,5,6,7,/*4*/4,1,2,5,9,/*5*/7,2,3,4,6,9,10,12,/*6*/7,3,5,7,8,12,13,14,/*7*/3,3,6,8,/*8*/4,6,7,14,15,/*9*/5,1,4,5,10,11,/*10*/4,5,9,11,12,/*11*/3,9,10,16,/*12*/5,5,6,10,13,16,/*13*/6,6,12,14,15,16,ENDNDEX,/*14*/4,6,8,13,15,/*15*/4,8,13,14,ENDNDEX,/*16*/4,11,12,13,

38、ENDNDEX,/*17*/0,0；/费用矩阵intconstpathFare1818=/*01234567891011121314151617*/TOC o 1-5 h z/*0*/0,3,1,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,/*1*/3,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,/*2*/1,1,0,1,2,1,0,0,0,0,0,0,0,0,0,0,0,0,/*3*/1,0,1,0,0,2,2,1,0,0,0,0,0,0,0,0,0,0,/*4*/0,1,2,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,/*5*/0,0

39、,1,2,0,0,1,0,0,3,1,0,3,0,0,0,0,0,/*6*/0,0,0,2,0,1,0,1,2,0,0,0,2,4,3,0,0,0,/*7*/0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,0,0,0,/*8*/0,0,0,0,0,0,2,1,0,0,0,0,0,0,1,3,0,0,/*9*/0,4,0,0,1,3,0,0,0,0,1,1,0,0,0,0,0,0,/*10*/0,0,0,0,0,1,0,0,0,1,0,1,2,0,0,0,0,0,/*11*/0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,1,0,/*12*/0,0,0,0,0,3,2

40、,0,0,0,2,0,0,2,0,0,1,0,/*13*/0,0,0,0,0,0,4,0,0,0,0,0,2,0,1,2,2,1,/*14*/0,0,0,0,0,0,3,0,1,0,0,0,0,1,0,1,0,0,/*15*/0,0,0,0,0,0,0,0,3,0,0,0,0,乙1,0,0,4,/*16*/0,0,0,0,0,0,0,0,0,0,0,1,1,2,0,0,0,1,/*17*/0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,4,1,0,;/查找符合条件的路径voidfindMoreShortPath(intindex,int*pointCount);检查路径是否符合条件BooleancheckPointOfPath(void