logo标签列表

使用Dijkstra算法找到哈密顿路径？

algorithmgraphdijkstrashortest-path
4

迪杰斯特拉算法能否找到从单个源顶点到所有其他顶点的所有最短路径，使得路径在无向对称图中恰好一次访问所有顶点？是否存在更快的对称图算法？

你能详细说明你想要什么吗？ - sukunrt
你可以多次访问顶点吗，还是必须只能访问一次？ - templatetypedef
@templatetypedef：每个顶点只出现一次，不允许重复？ - Micromega
3个回答
3
你所要求的是一种算法，用于找到图中从单个节点到每个其他节点的最短哈密顿路径（哈密顿路径是恰好经过图中每个节点一次的路径）。不幸的是，即使在无向图中确定是否存在一对节点之间的哈密顿路径也是NP完全问题，因此没有已知的多项式时间算法来解决这个问题（除非P = NP）。由于Dijkstra算法运行时间为多项式，因此没有已知的修改该算法以查找图中每个其他节点的哈密顿路径。希望这可以帮到你！
1

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

Bellman-Ford算法可能比Dijsktra更快，但仅适用于少数情况，并且此算法对具有负循环的图有效。

Dijkstra算法的最简实现结果为O（|E| + |V|^2）的运行时间。[|E|和|V|表示图的边和顶点。

有没有像Dijkstra算法一样遍历所有顶点而不是所有最短路径的算法？ - Micromega
这不就是O(V^2)吗，因为E受V^2的限制吗？ - zmbq
我认为OP的问题是关于使用Dijkstra算法找到哈密顿路径，而不仅仅是找到任意最短路径。 - templatetypedef
@Phpdna ~ 抱歉缺席了。你是指 Floyd-Warshall 算法吗？该算法将访问所有顶点，并旨在找到每对顶点之间的最短距离。 - Miki24
0
Dijkstra算法可以找到从一个选定点到其他所有点的最短路径。它适用于具有非负边缘的图形（有向或无向）。对于这种情况，没有更快的算法。
如果边缘权重有限制，则可能会有更快的算法。例如，如果权重限制为[0,1]，则可以使用BFS算法。
这可以推广到整数权重的情况，也可以使用更快的算法。（即，可以使用一组有限的数组而不是使用二叉搜索树）。
Dijkstra算法的复杂度如何？我不需要所有最短路径吗？或者当我只想要包含所有顶点的最短路径时，我需要使用单纯形算法或其他什么算法吗？ - Micromega
@sukunrt 是的，我认为那可能是答案，尽管有点难以确定需要什么。 - TooTone
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接