算法设计与分析：最短路径问题（哈密顿回路+最短路）小学期实践

给定一个n个结点，m条有向边（边权为正）的图，求出一条路径满足如下条件：

条件一：该路径可以从任意节点开始，不过起点和终点必须相同。

条件二：该路径除了起点和终点，其他结点都必须经过，且只能经过一次。

条件三：在满足上述两条件的前提下，要求路径尽可能短。

有两种搜索的思路，第一种就是在不考虑图的结构的前提下，枚举每一种可能的路径，这样的路径也就是 n n n个点的全排列，即 n ! n! n!种路径。之后对于枚举出来的路径，在根据具体的图的结构，判断其是否可行（是否确实连通），是否为最短路径。第一种时间复杂度显然就是：枚举出来的不同路径数*判断一条路径需要的时间，即： O ( n ! ∗ n ) O(n! * n) O(n!∗n)。

第一种方法的缺点就是没有非常有效的利用图的结构对搜索进行剪枝。所以我们想到第二种方法：对于每个节点，均枚举以它为起点的所有长度为n且每个节点只走一次的合法路径，同时维护当前路径总长度。这样我就不会枚举多余的不存在图中的边，此时如果图是完全图（ n n n个点， n ∗ n n*n n∗n条边），那么时间复杂度依然是 O ( n ! ) O(n!) O(n!)，但是对于稀疏图，此方法将极大地减少实际搜索量。