首先，源点是给定的，那么我要经过这三个点，必定经过这三个点的每一个点。这个路径一定是vs->va->vb->vc,{a,b,c}={i,j,k}，即abc是ijk的一个排列，因为是一条路径。然后，假定a,b,c己经确定，那么考虑其中的路径，vs->va，从s到a点，与bc无关，所以贪心取最短路p1，再考虑a->b，取最短路p2(从a到b的最短路)，再考虑b->c，取p3。这样，所得的p(min)=p1+p2+p3。注意只考虑了一种情况，而ijk的排列有3*2*1=6种，需要枚举6个的每一种情况。算法说明完成。现在来说明时间复杂度的问题。算法有两种实现方法，1.用dijstra算法，dijstra(u,v)为一函数，传出u，v之间的最短路，那么容易知道需要执行的为6*3=18次，是常数，时间复杂度O(n^2)2.bellman-ford算法，O(n^3)两个都行，还能优化。
|
