之前和我的小伙伴组队参加了华为2016的Code Craft比赛， 由于水平有限仅仅在初赛达到了67分的成绩，因为本人实在懒得抽筋，所以转载了小伙伴对所使用算法的介绍，原帖地址：http://www.wangerry.com/archives/wd516   强烈建议大家顺便去小伙伴的地盘逛逛，有干货喵

本题使用了贪心的思路。在此对使用的非递归深度优先路径搜索和Dijsktra算法进行简单的介绍。

对于比赛榜单中靠前的大神介绍，这个题应该是要用整数线性规划求解，目前个人水平不在这个层次，就简单的使用了深度优先搜索算法解简单用例，复杂用例使用基于贪心的分段路径Dijsktra算法求解。

该代码已在个人Git仓库开源：http://git.wangerry.com/wangerry/huawei_findpath。

题目介绍

1.  图中所有权重均为[1，20]内的整数；
2.  任一有向边的起点不等于终点；
3.  连接顶点A至顶点B的有向边可能超过一条，其权重可能一样，也可能不一样；
4.  该有向图的顶点不会超过600个，每个顶点出度(以该点为起点的有向边的数量)不超过8；
5.  V'中元素个数不超过50；
6.  从s到t的不成环有向路径P是指，P为由一系列有向边组成的从s至t的有向连通路径，且不允许重复经过任一节点；
7.  路径的权重是指所有组成该路径的所有有向边的权重之和。

对题目的分析

概览题目，题目主要的问题是针对一个图，求点s到t的最短路径，对于图中任意两点的最短距离现有的Dijkstra算法或Floyd算法都可以完美的求解，但是题目重点是要求经过必经点集。因此在这个要求下，所求的最短路径就和任意两点的最短距离没有任何关系了。图的规模也在逐步的扩大，所以对于简单用例我们可以用最直接暴力的DFS算法，而对于中高级用例使用了基于贪心的分段路径Dijsktra算法求解。按照华为的比赛用例，一共15个用例，其中前5个属于简单用例，中间5个属于中级用例，最后5个高级用例。不同等级的用例体现在图的规模，点的出入度规模及必经点的规模上。

数据结构定义

为求解这个题目，我们定义如下几个概念的数据结构：

点（Node）

对应图结构中的一个节点，属性有点的编号和出度边（Edge）集合。

边（Edge）

对应图结构中的一条边，属性有边的编号、边终点的引用和边的权重。

图（Graph）

对应图结构，属性有点的集合。针对Dijsktra搜算回溯添加了移除点编号集合（后面详细说明）。

路径（Path）

对应搜索结果表示的一条路径。属性有点集合（有顺序）及路径权重（按顺序的两点对应边的权重和）。

搜索状态（SearchStates）

用于Dijsktra搜索回溯记录搜索状态，属性有搜索起点引用，搜索终点引用，搜索起点到达其他必经点的最短路径集合，当前搜索图及必经点集合。

简单用例解法—非递归深度优先路径搜索DFS

对于图的最短路径求解，最直接简单的算法莫过于深度优先搜索DFS（Depth First Search）算法。但是这里不是在对图进行深度优先遍历，而是对所有可能的路径进行深度优先搜索，因此时间复杂度并非O（n²）。

说到DFS，普遍的做法是使用递归来做，这样做的好处是代码逻辑简单，但是由于我们搜索路径而非遍历图中所有的点，所以递归的深度理论上是全图最长的路径点个数，而且由于会不断的回溯，函数递归调用效率必然会非常慢，因此必须用非递归来实现。

下面对非递归深度优先路径搜索算法进行介绍，但是并非我们解题的算法，因为题目要求经过必经点集而且是求最短路径。因此实际的算法是在下面算法的基础上加入剪枝和判断完成的。

算法文字描述

1.  将当前搜索点(Point)指向全图搜索起点；
2.  如果Point为Null，则终止搜索，算法结束；否则进行下一步；
3.  如果Point已经出现在之前的搜索路径中（防止成环），则执行回溯算法，并执行第二步；否则执行第四步；
4.  如果Point不包含任何出度，则执行回溯算法，并执行第二步；否则执行第五步；
5.  将Point加入搜索路径（Path），将Point的出度边集合加入待选出度边集合堆栈（Stack），并将Point指向堆栈栈顶集合的第一个边对应的终止节点，执行第二步。

回溯算法：

1.  将Stack堆栈栈顶集合中的第一个元素边移除；
2.  判断如果Path不包含任何节点，将Point指向Null，算法结束，否则执行第三步；
3.  从Path中移除最后一个点；
4.  如果Stack堆栈栈顶集合中不存在任何元素，将该集合出栈，执行第六步；否则执行第五步；
5.  将Point指向栈顶集合的第一个边对应的终止节点，算法结束；
6.  如果Stack堆栈中元素为空，将Point指向Null，算法结束；否则执行第一步。

算法流程图

该题的解法

根据题目要求，我们需要求出最短路径且该路径包含所有必经点，那么我们需要在上述算法的基础上，加入两个剪枝条件：

1.  当搜索到的点为搜索终点时，停止继续搜索，判定当前搜索路径Path是否包含所有必经点，如果已经包含，则判定是否比已知路径最短，通过擂台法记录最短路径，并回溯。
2.  当前搜索路径的权重已经比记录的最短路径权重要大的时候，停止搜索并回溯（明显的剪枝条件）。

因此，对于该问题的实际解题算法的流程图如下：

实际搜索过程说明

为了能够详细的说明非递归深度优先路径搜索的过程，我以下面这个有向有权图（红色点为起始点和终止点，绿色点为必经点）为例，说明一下搜索过程：

由于需要说明算法中的各个条件情况，所以举了一个稍微复杂点的例子，否则不能覆盖所有的判断条件，但是相应就造成搜索过程较为复杂。

我们搜索从点A到F，必经（C | D | G）的最短路径，搜索过程如下：

详细版包含堆栈信息，路径信息，当前点及回溯原因等。简单版仅仅包含当前点，路径信息及简单的回溯原因，请根据自己的需要查看。

因此最终最短路径是：

点A->点B->点C->点G->点E->点D->点F（权重39）。

如果不要求经过必经点，很明显点A到F的最短路径为：

点A->点B->点D->点F（权重25）。

总结来说，就是类似于指针的思想结合堆栈记录待访问点进行非递归排序。

中、高用例解法—基于贪心的分段路径Dijsktra算法

可能有人会对这个标题提出疑问，因为Dijsktra算法的核心思想本来就是基于贪心的，什么叫基于贪心的分段路径。因为题目要求的“必经点”，Dijsktra算法可以很好的求出任意两点的最短路径，但是却无法解决必经点的问题。所以基于贪心的分段路径是指如下的算法：

1.  计算起点到所有必经点的Dijsktra，构成一个最短路径集Paths，并将当前必经点、图中的点保存为搜索状态；
2.  从路径集中根据某种算法选择一条路径P；
3.  从图中移除路径P中的所有点；
4.  从路径P的终点开始计算到剩余必经点的Dijsktra，构成新的最短路径集，并迭代该过程直到必经点为空；
5.  如果某点到剩余必经点计算Dijsktra，构成的最短路径集为空，则回溯到上一个搜索状态，根据选择算法选择一条新的路径继续进行；
6.  将每一步选择的路径首尾相连构成一条路径，当该路径包含所有必经点是停止搜索。

简单来说就是把必经点之间用最短路径一段一段的连接起来，其实这个方法非常的笨。而且基于贪心的算法，本身就在局部最优解的情况下极难得到全局最优解。而实际的情况更为糟糕，在多数大规模图的情况下我们都是在规定时间内得不到解。但是经过某些没有任何根据的参数调节（我称为玄幻调参），例如Dijsktra算法的待搜点集使用堆栈、队列、优先级队列等不同结构的情况，以及回溯进行1/3，1/2，1/4的状态跳越的情况下，事实证明对于求出解是有非常良好的效果的。但是我深知这其中的无根据纯粹是在撞运气，也是由于自己对图论、算法等方面知识的严重欠缺而做出的一种妥协。所以对于这部分内容不再详细说明。这里介绍一下Dijsktra算法的内容。

Dijsktra算法描述

Dijsktra算法实际计算的是单源点到达图中所有点的最短路径（对于图中任意两点的最短路径可以用Floyd算法）。其核心思想是我认为是如下命题的表述：

若路径P_t（经过点s, d₁, d₂, ... , d_n , t）是点s到t的最短路径，则路径P_m（经过点s, d₁, d₂, ... ,d_m）点s到d_m(d_m∈P_t)的最短路径。

例如若点A到F的最短路径是点A->点B->点D->点F，那么点A到点D的最短路径则是点A->点B->点D。（可用反证法求证）。

但是该命题是充分不必要的，因为若点A->点B->点D是点A到点D的最短路径，显然不能说明点A->点B->点D->点F是点A到点F的最短路径。除非我们能证明不存在任何一个路径，使得点A到点F的路径权重小于当前路径。如何证明不存在这条路径呢？ 我们只需要遍历全图，只要找到比这个路径短的路径就记录下来，不断地更新，当遍历完全图的时候，记录的路径一定是最短的。而由于上述命题的存在，使得我们正好可以在对图进行一次遍历的情况下就可以找到源点到所有点的最短距离。

那么具体到Dijsktra算法，我们需要维护三个数据结构：

1.  待访问点的优先级队列priorityQueue（权重小的在前）；
2.  最短路径点的（点-点）前驱表previousNode（记录路径的节点前驱关系）；
3.  源点到所有点的路径权重表weight。

算法过程如下：

1.  当前点Point -> 起点；
2.  初始化数据结构，将Point加入priorityQueue；记录Point的前驱关系，由于没有任何点可达Point，所以关系为Point->null；初始化到达所有点的权重为-1（表示不可达），Point本身的权重为0；
3.  遍历Point的所有出度点，认为从Point点可达这些出度点。判断出度点的路径权重表：
4.  如果为-1，则说明本来该点不可达，但可以从Point点到达该点，则更新该点的权重为这条出度边的路径权重，记录前驱关系出度点->Point，并且将该点加入priorityQueue（由于队列是有优先级的，所以加入的时候需要排序，权重小的在前）。
5.  如果不为-1，说明该点本来就可以到达，则判断权重，是原来的路径权重小还是现在小，如果现在的小，更新权重信息，并且更新前驱信息。
6.  直到priorityQueue为空时终止算法，也就是对图遍历完成时终止算法。
7.  从前驱表中，逆向找到到达该点的最短路径。

实际搜索过程说明

仍然以我们之前的图举例说明Dijsktra算法，因此先不包含必经点的内容：

待访问队列简称PQ，前驱表简称PN，路径权重表简称W。

结果路径是根据最后计算的前驱表PN，逆向推出的：

例如到点F的最短路径，可以从前驱表中找到如下关系

F->D, D->B, B->A, A->NULL。

因此最短路径为A->B->D->F。