是否有解决以下决策问题的算法：
给定一个由其转移矩阵定义的强连通加权有向图G，是否存在一个G没有负环的强连通跨越子图？
的强连通跨越子图是与共享相同顶点G的强连通子图。您可以查看本文以了解强连通跨越子图的定义。在本文中，他们提出了最小强连通子图问题的近似值。GG
解决这个问题的一种简单方法是使用 Ford-Bellman 或 Floyd-Warshall 算法找到图的负循环，从该循环中删除一条边，并在图仍然强连接时重复。但是这种幼稚的方法时间复杂度很差，因为我们可能会运行 Ford-bellman 算法并多次检查强连通性——而且我无法证明该算法是否在所有情况下都是正确的。
我希望在这里找到专家，他们可以告诉我这个决策问题是否可以在多项式时间内解决，以及什么算法可以解决。提前谢谢了。
这个问题通常是 NP 难的，这可以通过将哈密顿循环减少到其中来证明。
这是一个简单的解决方案，它有合理的机会找到一个在多项式时间内没有负循环的强连接跨越子图。但强调不能保证找到一个。
把所有的权重都变成负数。现在使用 Ford-Bellman 或 Floyd-Warshall 来寻找负循环。这实际上是原始图中的一个正循环。
现在我们在循环中选择一个顶点，并将其他顶点收缩到它。连接到/从已删除顶点的边被代表沿着该边并围绕循环移动到我们保留的那个的边替换。如果你在两个顶点之间有多个边，只保留最好的一个。
在新的、更小的图表上重复这个练习。
该算法在保证多项式时间内运行（每次迭代在多项式时间内运行并删除至少一个顶点）。如果它设法将您的图减少到一个点，那么您只需将过程倒退并发现您实际上已经找到了一个没有负循环的强连通跨越图。
但是，如果它不这样做，则不能保证没有。你只是没有找到它。
（我怀疑有保证的算法将是 NP 完全的。）