这个是一类比较开放的问题，个人认为还是属于图论的一个部分，但是他不能用现有的最短路径的相关算法比如SPFA，dijkstra算法来解决。曾今好像一个朋友问过我，是华为的一个什么比赛题目。这个题目用A*算法肯定可以，关键是在于如何去设计这个启发式函数？
相关知识你可以搜索
1.经过指定的中间节点集的最短路径算法
2.启发式搜索算法 A*

我觉得这题不太像是有多项式解法。（欢迎打脸）
设点数n，边数m，必须经过的边数k，n<=500,m<=5000,k<=500。
考虑暴力做法，O(n^3)预处理任意两点之间的最短路（当然也可以n次堆优化dijkstra，但这不是瓶颈），O(k!)枚举经过的k条边的排列并计算答案，总复杂度O(k!*k)，显然不能接受。
注意到最优解并不一定需要枚举全部排列才能得到，可以使用模拟退火等随机化算法获得较优解，使用合适的参数应该可以在大多数时候得到最优解。
我想尝试证明这个问题是NPC或NPH。
将原问题的m条边记为从from[i]至to[i]。
新建一个k个点的图，对k条指定边中的第i条和第j条，如果to[i]可达到from[j]，则在新建的图中从i向j连一条dis[to[i]][from[j]]的边。于是原问题问题在多项式时间内规约成新问题：在k个点的图中找出一条经过所有点的可重复路径，使路径长度最小。这个新问题看起来就很像NPC或NPH。（滑稽）
但是我还没有想好怎么把新问题规约回原问题。目前的想法是对新问题的每个点i，在原问题的i<<1到(i<<1)|1之间连一条+inf的边，对新问题的每条边i->j，在原问题的(i<<1)|1到j<<1之间连一条disi的边，但是好像会有些问题,还没有想清楚。

算法不懂，但是我知道一个通用的解决此类CSP问题的框架，你可以看一下：Optaplanner