[FEATURE]: Want to add Hamiltonian Path problem in JS repo.

[Jivan052]

Motivation

In backtracking, Hamiltonian problem is plays great role. Adding this file of program in JS & test file increase it's diversity.

Examples

Pathfinding Algorithms: This is useful for finding specific paths in graphs, such as city routing problems.

Puzzle Solving: Problems like the Knight's Tour in chess or Traveling Salesman Problem can have solutions inspired by Hamiltonian paths.

Game Development: In games where players need to visit locations without revisiting them (e.g., mazes or maps), this algorithm helps check the validity of paths.

Possible workarounds

Graph Theory Library: This program could be part of a broader graph algorithms library. You can add this class alongside other algorithms like DFS, BFS, Dijkstra, etc.

Puzzle Solvers: Hamiltonian paths are used in puzzles and games, and this program could be a part of a game engine that checks valid paths or graph traversal.

Educational Projects: If your open-source project is educational (focused on algorithms and data structures), this could serve as a solid example of backtracking and graph traversal.

Additional information

No response

[Jivan052]

@HRIDYANSHU054 kindly assign this issue to me

[HRIDYANSHU054]

@Jivanjamadar I don't have the necessary permissions to do that, you should ask a maintainer.

[Jivan052]

@vbrazo kindly assign this issue to me

[appgurueu]

Sure, but please implement the Held-Karp algorithm. The naive "enumerate all permutations" algo (1) doesn't add much vs. generate permutations etc. which we already have; (2) is much slower (exponential vs factorial).

[Jivan052]

@appgurueu You mean, I have to implement Held-Karp algorithm to just calculate minimum cost to visit all cities in TSP ( travelling salesman) or implement both Held-Karp algorithm and hamiltonian algorithm in program to find Hamiltonian path & minimum cost to visit all cities at once. Please, clarify so i can start to write program.

[appgurueu]

@appgurueu You mean, I have to implement Held-Karp algorithm to just calculate minimum cost to visit all cities in TSP ( travelling salesman)

Sure, implementing it as a solution to the TSP problem also works, and is more useful, since Hamiltonian cycle is just a special case of the TSP. (And Hamiltonian path can be reduced to Hamiltonian cycle.)

or implement both Held-Karp algorithm and hamiltonian algorithm

I'm not aware of a "hamiltonian algorithm" related to this. Please do not confuse algorithm and problem.

The Held-Karp algorithm can be used to solve the Hamiltonian cycle (and thus the Hamiltonian path) problem more efficiently than the naive algorithm of enumerating all permutations, again because it's essentially a special case of TSP.