我想在加权有向图中找到正好由4条边组成的最短圈（最短=边的权的最小和）。
我知道我可以使用floyd–warshall算法来寻找图中的最短周期，如here所述。但我不知道如何找到由四条边组成的最短循环。
最佳答案
既然你提到了floyd warshall，我认为拥有邻接矩阵不是问题。
让我们这样看：长度为4的循环的形式是a->b->c->d->a。
把它分成两对边：a->b->c和c->d->a。
给定邻接矩阵，我们可以很容易地用两条边计算最短路径矩阵：从x到z的最短路径是每个顶点x->y->z的y的最小值。
给出最小值的顶点也可以存储，如果我们需要表示循环，而不仅仅是它的长度。
现在，要找到长度为4的最短循环，只需遍历所有可能的对y。
对于每一对，我们有两条边从(a, c)到a的最小旅行成本和两条边从c到c的最小旅行成本。
这两个成本之和最小的一对给了我们期望的周期。
该解决方案在O（n^3）中运行，并有O（n^2）个附加内存。
关于algorithm - 在图中找到最短的四边循环，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29581356/