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

Question

这是问题的链接

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

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

标签： algorithmgraphpathgraph-theory

Answer 1

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