用Dijkstra算法寻找哈密顿路径？

Question

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

Answer 1

您需要的是一种算法，用于查找从图中的单个节点到每个其他节点的最短Hamiltonian paths (哈密顿路径是指恰好经过图中每个节点一次的路径)。不幸的是，即使是确定无向图中两个节点之间是否存在哈密顿路径的问题也是NP完全的，因此没有已知的多项式时间算法来解决这个问题(除非P=NP，否则它们不存在)。由于Dijkstra的算法在多项式时间内运行，因此该算法没有已知的修改，可以找到到图中每个节点的哈密顿路径。

希望这能有所帮助！

Answer 2

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

Bellman-Ford算法比Dijsktra算法更快，但仅在极少数情况下，该算法适用于具有负圈的图。

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

Answer 3

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

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

这可以推广到具有整数权重的情况，也可以使用更快的算法。(即，代替使用二进制搜索树，可以使用有限的数组集合)。