我有另一个想法.由于该图是非循环图，因此我们可以将必需节点(源节点和目标节点除外)分为两个节点( A 到 A _start )， A _end )并在它们之间设置一条边，并将权重设置为-infinity.强制节点 A 的所有传入边缘都将连接到 A _start ，而强制节点 A 的所有传出边缘都将连接从 A _end 中出来.最后，我们将对源节点到目标节点运行dijkstra算法.由于我们在必选节点中设置了-infinite权重，因此dijkstra必须通过它们以使成本最小化.另外，由于该图是非循环图，因此我们不必担心负循环.

I have another idea. Since the graph is acyclic graph, we can split the mandatory node (except source and destination node) into two node (A to A_start and A_end) and set an edge between them and set the weight as -infinity. All incoming edge to mandatory node A will be connected to A_start and all outgoing edge from mandatory node A will be came out from A_end. Finally we will run a dijkstra algorithm for source node to destination node. Since we set an -infinite weight in mandatory node, dijkstra is bound to go through them to minimize the cost. Also as the the graph is acyclic graph, we don't have to worry about negative cycle.