最短路径算法问题某网络拓扑结构为图G＝（V，E），其中V＝{V1,...,Vi,...,Vn}为顶点集合，1

Question

最短路径算法问题
某网络拓扑结构为图G＝（V，E），其中V＝{V1,...,Vi,...,Vn}为顶点集合，1

Answer 1

首先，源点是给定的，那么我要经过这三个点，必定经过这三个点的每一个点。
这个路径一定是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)
两个都行，还能优化。