比赛的算法题，关于有必经点等条件约束下图的最优路径问题，集思广益，指点一二，谢谢大家。

[wuyukai]

先简单介绍下题目要点，如下图

1. 黄点 S、E 分别表示起点（ Start ）和终点（ End ），这个已经给定。
2. 绿点 N7、N12 为必经点，这个虽给定，但算法应能接收参数来设定必经点并能处理任意必经点问题。
3. 绿线 N2<-->N4、N13<-->N14 必经路线，同上，应该可接收参数指定并处理。
4. 红线 N11<-->N12 不能通过的路线。
5. 无向，点可重复通过，权值等信息具体看图。

强调一下，所有条件都很宽松，在得到路径的过程中可以舍弃一些之前列举的条件，比如给出的答案必经点只经过一个点，必经路线只经过一条，权值不一定最小，经过点数不一点最少等等。所以给出的最优解，可能是满足部分条件的解，解的个数应该也是多个。（以上个人对题意理解，应该是没偏差的）

然后说一下我自己目前的思路：

核心：Dijkstra 算法，计算固定两点之间的最短距离。

关于满足条件的解决思路

1. 关于红线，这个好办，直接可以从构图的方向上改，将两点之间的距离改为无穷大或者二者不相邻来解决。
2. 关于绿线和绿点，两个线段，两个点，可以看成 6 个必经点，并且 6 个点有两组是总是相邻的，将这种情况排列组合，列举出所有这 6 个点符合条件的搭配，然后针对每一条线路，相当于线路的顺序已经定下来了，只是到达每个点的方式还未定，因为这样可以看成固定点之间求最短距离，用 Dijkstra 就可以得到两两点之间的路径，将这些路径串起来，就是当前得到的最优，然后将所有情况遍历，得到最后的最优解。
3. 增加了一些自己的特色：Dijkstra 的限制，只能得到一条最短路径，即使有两条长度一样短的，它也只会给你一个结果。所以我修改了一下 Dijkstra 的搜寻方式和结算最短路径的方式，把到任意点的所有长度相等的最短路径都打印出来，当然也可以选择经过节点数最少的路径。

目前三个的小队伍在做，结果已经能出来了，也能验证结果（当然也可能会有一些隐藏的小 Bug ）。但是感觉这种方式效率有点低，所以来问问大家有没有好的思路，取取经，欢迎大家提意见，在这先谢了。

PS：顺便问一下，像这种小算法题，找工作的时候有没有微小的作用呢，有个什么样的比重呢，应该会有个映像分吧。

PPS：顺便说一下 Mac 怎么没搞个上下分屏呢，像这样的“微小项目”上面 Atom 下面 iTerm2 还是蛮爽的哈哈。

[mickeyandkaka]

中兴的比赛吧。
https://cs.stackexchange.com/questions/14390/find-a-simple-path-visiting-all-marked-vertices
显然最优解是 NP，把必须经过的边，转化成点，然后状压 DP 就行了。

这种小数据没什么意思。

[MForever78]

楼主，你这样在这里公开地问比赛的题目，这样符合规则吗？

[wuyukai]

@MForever78 这种题不是大把非常非常常见？贴个图只为解释的更清楚，如果不合适就联系站长移除吧 @Livid

[mickeyandkaka]

@wuyukai 主要是图都是题目里面的。。。

[wuyukai]

@mickeyandkaka 可是最后算法肯定是通用的呀，给定任意一个类似的图，给定任意类似的条件，然后计算出结果，现在这个图根本说明不了任何问题啊，只是个参考，写出来的算法肯定不是针对这一个图啊，不然还有什么用。

[flowfire]

算法废表示我只能想到广度优先……………

[Weixk]

这个有点类似去年华为软挑题目，就是不知道图的规模。如果有几百上千个节点用 Dijkstra 肯定是不行了，得用启发式算法，如蚁群算法这种。。

[wuyukai]

@Weixk 好的谢谢思路，我去研究一下。