本文主要是介绍2017年中兴算法大赛 迪杰特斯拉派，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
总结：本人2017年参加的比赛，对于初次参加算法大赛的作者来说，异常激动又有点小窃喜，最后在赛区拿到24名的名次，名次不算高，但是对于一步步解决问题过来的我，经验与经历更为重要，再次做一个小小的总结，也对后续算法提出自己的改进意见，希望对后面参加比赛的你们有一点点启发。
1. 试题介绍
## 赛题 ##最强大脑中的收官蜂巢迷宫变态级挑战，相信大家都叹为观止！最强大脑收官战打响后，收视率节节攀升，就连蚁后也不时出题难为一下她的子民们。在动物世界中，称得上活地图的，除了蜜蜂，蚂蚁当仁不让。在复杂多变的蚁巢中， 蚂蚁总是能以最快、最高效的方式游历在各个储藏间（存储食物）。今天，她看完最新一期节目，又发布了一项新任务：小蚁同学，我需要玉米库的玉米，再要配点水果，去帮我找来吧。小蚁正准备出发，蚁后又说：哎呀，回来，我还没说完呢，还有若干要求如下：
1.小蚁同学，你需要尽可能以最少的花费拿到食物（附件图中路线上的数值表示每两个储物间的花费）；
2.小蚁同学，你最多只能经过9个储藏间拿到食物（包含起止两个节点，多次通过同一节点按重复次数计算）；
3.小蚁同学，你必须经过玉米间，水果间（附件图中标绿色节点）；
4.别忘了，食蚁兽也在路上活动呢，一旦与食蚁兽相遇，性命危矣！不过小蚁微信群公告已经公布了敌人信息（附件图中标红色路段）；
5.最后，千万别忘了，还有两段路是必须经过的，那里有我准备的神秘礼物等着你呢(附件图中标绿色路段)。
这下小蚁犯难了，这和它们平时找食物的集体活动规则不一样嘛,看来这次需要单独行动了。要怎么选路呢？小蚁经过一番苦思冥想，稿纸堆了一摞，啊，终于找到了！亲爱的同学们，你们能否也设计一种通用的路径搜索算法，来应对各种搜索限制条件，找到一条最优路径，顺利完成蚁后布置的任务呢？
注：
1、蚁巢，有若干个储藏间（附件图中圆圈表示），储藏间之间有诸多路可以到达(各储藏间拓扑图见附件);
2、节点本身通行无花费；
3、该图为无向图，可以正反两方向通行，两方向都会计费，并且花费相同；
4、起止节点分别为附件图中S点和E点。
5、最优路径：即满足限制条件的路径。
2. 赛题分析
从赛题中，可以简化归纳一下题目的几个要求，首先从S点出发，终点是E，图中寻找最优路径，其中N2-N4，N13-N14为必走线段，N7,N12为不可走的点，N12-N11为不可走的线段，要求在九个点之内，到达终点，起点终点，计算在内，九点走不完，求次优路径。
3. 赛题解析
限制节点算法分析
限制算法关键点提示：
1.必经线段处理：在经过线段一个端点以后，下一步直接经过另一个端点，而不会经由其他节点再绕回另一端点，迪杰斯特拉是通过计算比较最短步长确定下一个节点的，那么，在遇到必经线段的一个端点时，则跳过计算步长比较，直接将另一个端点定为下一个经过节点即可。
2.不可经过线段处理：因为图的存储是利用HashMa来存储节点以及节点之间的步长信息的，因为可以直接在查询操作前，将不可经过节点之间的步长直接删除，简化操作。
3.必经节点处理：令0为起点，分别求出起点到每个必经节点的步长，找到步长最短的必经节点为第一个经过的必经节点（已达节点就可以不用计算了），然后以此为起点，重复上述操作，直到所有必经节点都经过以后，最后到达17终点。
4. 代码分析
对于迪杰斯特拉算法，网上有很多介绍，也有现成的代码，大同小异，本人在拿到赛题以后，也是查阅了很多资料，最终采用了这位博客的代码作为基础来进行后续的延伸，http://blog.csdn.net/xiaojimanman/article/details/50889670，他写的非常的有条理而又清晰，代码完全可以运行，所以我也是非常感谢这位前辈。
拿下迪杰特斯拉基础算法以后，我们可以把赛题的题按照代码的输入的格式进行修改，比较无聊，图很大就麻烦了，很多人采用了矩阵，利用写好的规范图数据，通过代码读取配置文件来加载图，感觉这样更方便，可以采用。
4.1 限制点路径排序
题目要求必经线段可转化为必经点N2与N4, N12与N11，但是只要出现，必成对出现，如果排到N2，则后面强制排序N4，以此类推。
这篇关于2017年中兴算法大赛 迪杰特斯拉派的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
