Search for Hamiltonian paths with Dijkstra's algorithm?

Question

Can the Dijkstra algorithm find the shortest path from one source vertex to all other vertices in such a way that the path visits all vertices in an undirected and symmetric graph once and exactly once? Is there a faster algorithm for a symmetrical graph?

Answer 1

What you are asking for is an algorithm for finding the shortest Hamiltonian paths from one node to another node in (the Hamilton path is the one that goes through each node in the graph exactly once). Unfortunately, the problem of even determining whether a Hamiltonian path exists between a pair of nodes in an undirected graph is NP-complete, and therefore there are no known polynomial time algorithms that solve this problem (and they do not exist if only P = NP). Since Dijkstra’s algorithm runs in polynomial time, there is no known modification of this algorithm that will find the Hamiltonian paths to each other node on the graph.

Hope this helps!

Answer 2

Yes, Dijkstra’s algorithm will help you find the shortest path from both directional and undirected graphs. But this is more useful when using a directed graph.

The Bellman-Ford algorithm can be faster than Dijsktra's, but only in a few cases, and this algorithm is valid for graphs with a negative cycle.

The simplest implementation of Dijkstra's algorithm leads to runtime for O (| E | + | V | ^ 2). [| E | and | V | denoting edges and vertices of the graph.

Answer 3

Dijkstra's algorithm finds the shortest path from one selected point to all the others. It is defined for a graph (directional or not) with non-negative edges. There is no faster algorithm for this case.

If there are restrictions on the weight of the edges - there may be a faster algorithm. For example, if the balance is limited [0,1] - the BFS algorithm can be used.

This can be generalized to the case with integer weights, you can also use a faster algorithm. (i.e., instead of using a binary search tree, you can use a limited set of arrays).