无向图最短路径.pdf

一、问题重述

最强大脑中的收官蜂巢迷宫变态级挑战，相信大家都叹为观止！最强大脑收官

战打响后，收视率节节攀升，就连蚁后也不时出题难为一下她的子民们。在动物世

界中，称得上活地图的，除了蜜蜂，蚂蚁当仁不让。在复杂多变的蚁巢中，蚂蚁

总是能以最快、最高效的方式游历在各个储藏间（存储食物）。今天，她看完必威体育精装版

一期节目，又发布了一项新任务：小蚁同学，我需要玉米库的玉米，再要配点水果，

去帮我找来吧。小蚁正准备出发，蚁后又说：哎呀，回来，我还没说完呢，还有若

干要求如下：

1.小蚁同学，你需要尽可能以最少的花费拿到食物（附件图中路线上的数值表示

每两个储物间的花费）；

2.小蚁同学，你最多只能经过9个储藏间拿到食物（包含起止两个节点，多次通

过同一节点按重复次数计算）；

3.小蚁同学，你必须经过玉米间，水果间（附件图中标绿色节点）；

4.别忘了，食蚁兽也在路上活动呢，一旦与食蚁兽相遇，性命危矣！不过小蚁微

信群公告已经公布了敌人信息（附件图中标红色路段）；

5.最后，千万别忘了，还有两段路是必须经过的，那里有我准备的神秘礼物等着

你呢(附件图中标绿色路段)。

这下小蚁犯难了，这和它们平时找食物的集体活动规则不一样嘛,看来这次需

要单独行动了。要怎么选路呢？小蚁经过一番苦思冥想，稿纸堆了一摞，啊，终于

找到了！亲爱的同学们，你们能否也设计一种通用的路径有哪些信誉好的足球投注网站算法，来应对各种搜

索限制条件，找到一条最优路径，顺利完成蚁后布置的任务呢？

注：

1、蚁巢，有若干个储藏间（附件图中圆圈表示），储藏间之间有诸多路可以到达(各

储藏间拓扑图见附件);

2、节点本身通行无花费；

3、该图为无向图，可以正反两方向通行，两方向都会计费，并且花费相同；

4、起止节点分别为附件图中S点和E点。

5、最优路径：即满足限制条件的路径。

图1

1

二、模型假设与符号说明

2.1模型假设

1.因为题目中并未明确给出是否是从起始点开始到达终止点，即从s到e，为

防止歧义、方便计算，假设每条路径都是从起点到终点；

2.下文中说到的点或点数均代表存储室或存储室数量；

3.通过图1各路段关系，可以假设，为得到最优路径，不会再从N1、N2、N3

走回起点。

2.2符号说明

符号含义

N最多经过的点的个数

经过的第n个点

第j个集合个点中的第i的数值，即将要走向的下一个点

第j个点所有与其相邻的点的集合

和第k个点相邻的点的总数

走过的第k个点集合元素的下标，从0到-1

走第k条路所需要的总费用

从编号为i的点到编号为j的点的费用，即表3i行j列对应的值

表1

三、问题分析

3.1整体分析

题目的总体思路是在各种约束条件下求出一条从起点到终点的最优路径，最优

可以说是有两个方面：第一是经过的储藏室即经过的点最好，题目中给定为9个，

第二是在途中花费的费用最少。基于以上分析，我们决定建立无向图最优路径模型，

从通过的点数和费用进行优化。

3.2约束条件分析

（1）题目中并未明确给出是从起始点到达终点（即图中给出的s和e），为了

不产生歧义，以及方便计算，我们在假设中规定该路线是从起始点到达终点（即图

1中给出的s和e）。

（2）最多只能经过9个储藏室（即9个点）

（3）必须经过两条绿色的路线，即必须经过N2、N4、N13、N14，并且N2

和N3相邻，N13和N14相邻。

（4）必须经过水果间和玉米间，即必须经过N7