寻找最低代价路径的无向图算法
寻找最低代价路径的无向图算法
提问于 2015-07-16 01:20:51
我知道一些算法能够找到有向图的最低成本路径(就像Dijkstra和Floyd一样)。有没有适用于无向图的算法？
我的问题是:我需要找到从a到b通过所有顶点的最低成本路径(无向图)。
回答 2
Stack Overflow用户
发布于 2015-07-16 01:27:31
我的问题是:我需要找到从a到b通过所有顶点的最低成本路径(无向图)。
这是Traveling Salesman Problem，也就是NP-Hard，因此没有已知的有效解决方案。
但是，如果图相当小，有一些技术可以(在指数时间内)以最佳方式解决它，如Dynamic Programming。
通常，将无向图更改为有向图相当容易，可以通过将无向边{u,v}更改为两条有向边(u,v)和(v,u)来完成
Stack Overflow用户
发布于 2015-07-16 01:26:58
假设您有非负的边值，您可以将无向图中的每条边视为有向图中的两条边，其中一条边指向或来自连接的顶点。然后，您可以使用许多算法中的一种，包括您列出的算法。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/31436991
复制相关文章
相似问题
腾讯云开发者
