小编hol*_*ola的帖子

是否有一种算法可以解决以下决策问题：

给定一个G由其转移矩阵定义的强连通加权有向图，是否存在一个G没有负循环的强连通生成子图？

的强连通生成子图G是与G共享相同顶点的强连通子图G。您可以查看本文以了解强连接生成子图的定义。在本文中，他们提出了最小强连通子图问题的近似。

解决这个问题的一个简单方法是使用 Ford-Bellman 或 Floyd-Warshall 算法找到图的负循环，从这个循环中删除一条边，并在图仍然强连通时重复。但是这种简单的方法时间复杂度很低，因为我们可能会运行福特贝尔曼算法并多次检查强连通性——而且我无法证明这个算法是否在所有情况下都是正确的。

我希望在这里找到专家，他们可以告诉我这个决策问题是否可以在多项式时间内解决，以及什么算法可以解决这个问题。提前谢谢了。