e********r
发帖数: 2352 | 1 一个Graph,求最短路径，一个路径如果经过几个特定点会有一个extra weight，比如说
，单独经过A点，单独经过B点都是用正常的weight，但是如果这个路径同时经过A,B，
那就给这个路径设定一个extra weight，这样一个Graph，请问有什么好的算法吗. | z**********6
发帖数: 68 | 2 我给出一个递归算式：假设从s点出发t点到达，那么s到t最短路径L(s,t)=min{extra
weight +(L(s,A)+L(A,B)+L(B,t)), extra weight + (L(s,B)+L(B,A)+L(A,t)), L(s,A
)+L(A,t), L(s,B)+L(B,t),L(s,t)(不经过A或B)}
如果特殊点(A,B)数量少的话，这个等式可以在非指数递增的情况下推广，如果特殊点
数量巨大或者说是变量的话，那我怀疑这个问题跟哈密顿路径一样是NPC的。 | W***o
发帖数: 6519 | 3 priority queue with your comparator
【在 e********r 的大作中提到】
: 一个Graph,求最短路径，一个路径如果经过几个特定点会有一个extra weight，比如说
: ，单独经过A点，单独经过B点都是用正常的weight，但是如果这个路径同时经过A,B，
: 那就给这个路径设定一个extra weight，这样一个Graph，请问有什么好的算法吗.
|
|
