hit*_*ish 3 algorithm graph-algorithm
这是我遇到的面试问题:
您将获得一个国家城市之间的飞机地图,基本上有一个有向图,其中权重是城市之间飞机的成本.您还获得了一张优惠券,可以在任何一个航班上获得50%的优惠券.查找您可以在两个城市之间旅行的最低费用？
这个问题的基本算法是Dijkstra的最短路径算法.但是,我们需要找到一种方法来包含优惠券.
我们可以通过介绍优惠券状态来做到这一点.这是available或者spent.在每个机场,州都可以是两者之一.所以我们可以复制顶点的数量(对于机场).对于每个机场,一个顶点将具有available状态,一个顶点将具有该spent状态.边缘必须稍微改变.从具有spent状态的顶点到具有状态的顶点是不可能的available.在另一个方向,原始成本减半.
现在我们想要找到从起始机场(带available状态的顶点)到目的地机场(具有状态的顶点)的最小成本路径spent.这可以通过Dijkstra的普通算法来实现.