在O（n^2）中，我一直致力于寻找加权无向图中最便宜圈的算法循环不必访问图中的每个顶点（即，我不寻找哈密顿循环）。
有人能帮我找个策略吗？
加权无向图的一个例子：
最佳答案
我不确定O（n^2）时间界限是从哪里来的。明显的O（n（m+n logn））时间算法是，对于每个顶点，从该顶点计算一个最短路径树，然后考虑由非树边和一些树边构成的基本循环。
关于algorithm - 在无向加权图中找到最便宜的周期，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23924010/