NP-Complete证明求助
假设有一个图，G=(V,E)，每一条边有一个权值(weight)。设定起始端点Vs和Vd，假设图G中有多条连接Vs和Vd的路径(path)，现在求一条路径p，使得函数F=(W(p), |p|)具有最大值，其中W(p)指的是这条路径的权值(也就是这条路径上面所有边权值的最小值)，|p|指的是路径长度，也就是路径p上边的个数。很明显，对于一条路径p，W(p)和|p|是两个独立变量，两者之间没有关系。
个人感觉这个问题是一个两个变量的NP-Complete问题，相信也有类似问题的证明，但是羞于小弟涉猎面不广，至今未发现类似问题的证明，希望各位前辈指教。
[解决办法]
原来你这个F是这个样子的……我大概知道了。
这显然有多项式算法的。最关键的是利用两个性质。
1. w(p)=min(d(p))
2. F关于第二个参数
[解决办法]
p
[解决办法]
递减
因此有一个最关键的性质是，如果w(p)确定的话，那么F最大当且仅当路径p是最短的。
所以多项式办法如下。枚举边e=(u,v)，把它当做最小边。做子图G'使得G'只包含>=d(e)的所有边。这时只需要做G'包含边e的s->t最短路径……而这个最短路径也就是s->u,v->t的最短路径然后粘上e这个边。求出最短路径以后算F就很容易了。
