给定无向连接图的两个节点之间的最短路径数

Question

这是问题的链接

https://www.hackerearth.com/challenges/hiring/american-express-technology-software-engineer-2019-batch/algorithm/number-of-shortest-path-046c75d6/

我无法理解我应该如何处理这个问题。

Answer 1

如果图是非循环的，你只能用拓扑排序来解决这个问题。您需要从开始顶点对图进行排序，之后您需要按拓扑排序顺序计算所有顶点的答案。顶点的答案将是他所有父母从传入边的答案的总和。 如果图是循环的，你可以通过搜索最大流量来解决这个问题。你的源将是开始，汇将是结束。之后的答案将是这两个顶点之间的最大流量。