4

Dijkstra 算法能否找到从单个源顶点到所有其他顶点的所有最短路径，使得该路径访问无向和对称图中的所有顶点一次且恰好一次？对称图有更快的算法吗？

4

3 回答 3

3

您所要求的是一种算法，用于找到图中从单个节点到每个其他节点的最短哈密顿路径（哈密顿路径是通过图中每个节点恰好一次的路径）。不幸的是，甚至确定无向图中的一对节点之间是否存在哈密顿路径的问题都是 NP 完全的，因此没有已知的多项式时间算法可以解决这个问题（而且它们也不存在除非 P = NP）。由于 Dijkstra 的算法在多项式时间内运行，因此对该算法没有已知的修改可以找到到图中每个其他节点的哈密顿路径。

希望这可以帮助！

于 2013-06-08T21:14:32.023 回答
1

是的，Dijkstra 的算法将帮助您找出有向图和无向图中的最短路径。但是当使用有向图时它更有用。

Bellman-Ford 算法可以比 Dijsktra 更快，但仅在少数情况下，该算法对负循环图有效。

Dijkstra 算法的最简单实现导致 O(|E|+|V|^2) 的运行时间。[|E| & |V| 表示图的边和顶点。

于 2013-06-07T05:06:09.647 回答
0

Dijkstra 算法找到从一个选定点到所有其他点的最短路径。它是为具有非负边的图（有向或无向）定义的。对于这种情况，没有更快的算法。

如果边缘权重有限制 - 可能会有更快的算法。例如，如果权重限制为 [0,1] - 可以使用 BFS 算法。

这可以推广到具有整数权重的情况，也可以使用更快的算法。（即可以使用一组有限的数组，而不是使用二叉搜索树）。

于 2013-06-07T03:59:44.273 回答