You can solve this problem by reducing it to a problem with maximum flow in the graph appropriately. The idea is this:
- Divide each node v in the graph into nodes: v in and v out .
- For each node v add the edge of the capacitance one of v in to v out .
- Replace each other the edge (u, v) in the graph with the edge from u out to v in capacity 1.
- Add node t to the new highlighted destination.
- For each of the target nodes v, add an edge from v to to t with a capacity of 1.
- Find the maximum flow from s out to t. The stream value is the number of node-disjoint paths.
The idea of this design is as follows. Any flow path from the start of node s to the destination node t must have a capacity of one, since all edges have a capacity of one. Since all capacitors are integral, there is an integral max flow. No two flow paths can go through the same node broker, because when passing through a node in a graph, the flow path must cross the border from v in to v out , and the capacity here is limited. In addition, this flow path should arrive at t, ending at one of the three special nodes that you identified, then following the edge from node to t. Thus, each stream stream represents a node-disjoint path from the source node s to one of the three target nodes. Accordingly, calculating the maximum flow here corresponds to finding the maximum number of node-disjoint paths that you can take from s to any of the three destinations.
Hope this helps!