我知道一些算法能够为有向图找到成本最低的路径(就像 Dijkstra 和 Floyd)。 有没有适用于无向图的算法？
我的问题是:我需要找到从 a 到 b 通过所有顶点(无向图)的最低成本路径。
最佳答案
My problem is: I need to find the lowest cost path from a to b passing through all vertexes (non-oriented graph)
这是 Traveling Salesman Problem ，即 NP-Hard , 所以没有已知的有效解决方案。
然而，如果图相当小，有一些技术可以最优地解决它(在指数时间内)，比如 Dynamic Programming .
通常，将无向图更改为有向图相当容易，只需将无向边 {u,v} 更改为两条有向边 (u,v) 和 (v,u)
关于algorithm - 寻找最低成本路径的非有向图算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31436991/