Stack Overflow
Stack Overflow

Questions tagged [hamiltonian-path]

24 questions
69
votes
9 answers

Difference between hamiltonian path and euler path

Can some one tell me the difference between hamiltonian path and euler path. They seem similar!
mousey
  • 11,601
  • 16
  • 52
  • 59
1
vote
1 answer

Hamiltonian Paths in Python with Arbitrary Starting Positions

I'm currently working on a project in my spare time where I need to check for the existence of a Hamiltonian path within a graph, however, it doesn't matter where the path begins or ends, only that one exists within the graph. I copied this code…
Matthaeus Catuvellauniensis
  • 13
  • 2
1
vote
0 answers

Is there an algorithm for finding no. of k-weights hamiltonian paths in a 0-1 complete digraph

I have a complete directed graph with n vertices. The edges are having 0-1 weights (i.e, they can have 0 or 1 as there weights). Also 1-weight edges are sparse i.e, there does not exist a hamiltonian path with more than n/2 weight. The problem is to…
Arpit Kesharwani
  • 11
  • 2
1
vote
0 answers

Hamiltonian Path Algorithm on Directed Unweighted Graph uses non-existent edges

I am trying to implement the Held-Karp algorithm for finding a Hamiltonian path on an unweighted directed graph. In order to achieve this I have created an inner class Combination which stores a Stack which represents the order of the path taken and…
Dave
  • 33
  • 4
1
vote
0 answers

Travelling salesman without returning to the starting point

My question is - if we consider the Travelling salesman problem without the returning to the starting point part does the greedy (nearest neighbor) algorithm solves this problem correctly ? In a previous thread someone stated that this problem is…
Dannynis
  • 73
  • 4
0
votes
1 answer

Couldn't get the required correct output

I'm trying to solve the Hamiltonial cycle and path problem using backtracking method whether a source vertex is given for the input graph. When all the vertex are visited in that input graph, then the path will be displayed. Using backtracking…
Suman Bhattacharya
  • 1
0
votes
0 answers

Dummy node for TSP and finding shortest Hamiltonian Path

Can anyone provide assistance to the problem I'm facing? I'm working on implementing a delivery system algorithm. I have attempted to solve it using a graph, where addresses are represented as nodes and the distance between nodes as the weight of…
IlayAsayag
  • 1
  • 1
0
votes
0 answers

I keep getting KeyError:0 message when I run the code

I keep getting an error message like "KeyError:0" for this code when I ran it. The code is in two parts ("get_qubit_op(dist), and exact_solver(problem, converter)"). The first part does not give me any error but the second part gives me an error…
Facts and Facts
  • 1
  • 1
0
votes
1 answer

Why does the existence of a Hamilton path in a Directed Acyclic Graph (DAG) show there is single way to topologically order the DAG?

Here is my understanding- we can find a Hamilton path by topologically sorting a DAG and checking if an edge exists between each vertex in this sorted order. And that somehow this shows that this topological order is the only one that can exist. How…
mary doesy
  • 3
  • 3
0
votes
0 answers

Is this code to find path into square grid using backtracking is right?

I was reading antti lakesonen's competitive programming handbook and I came across backtracking for finding grid paths with some optimizations applied. In nutshell here are the rules for a valid path across the grid : 0. Path search starts from top…
Patel Yash
  • 21
  • 1
0
votes
2 answers

Hamiltonian paths by total cost

I am trying to calculate Hamiltonian paths, paths that visit every node in a graph once, by a range of desired total costs or total edge lengths. There are various algorithms for the Traveling Salesman problem that calculate the shortest path, but I…
RJ Adriaansen
  • 9,131
  • 2
  • 12
  • 26
0
votes
1 answer

An efficient Algorithm for Hamiltonian circuit

I recently discovered the Hamiltonian Path/Circuit in CodeBullet's Snake A.I. video and decided to give it a go myself. I wrote a basic Depth First Search algorithm to visit all the nodes in a graph and store the path when the circuit is…
Ahmed Mustafa
  • 119
  • 1
  • 11
0
votes
1 answer

Ultra-Hamiltonian cycle

Ultra-Hamiltonian cycling is defined to be a closed walk that visits every vertex exactly once, except for at most one vertex that visits more than once. Question:- Prove that it is NP-hard to determine whether a given graph contains an…
Nitin Kumar Chauhan
  • 35
  • 4
0
votes
0 answers

How to efficiently find all Hamiltonian paths in an undirected graph, withou just using DFS?

I have problem where i need to display all nodes which are included in a path(from source to destination), but in such a way that we visit every node in the path only once. Solution with only DFS (and marking visited elements) is not fast…
Una3
  • 15
  • 1
0
votes
2 answers

Problem in R studio while solving Traveling Salesman Problem (TSP) using Concorde

I am working with Concorde to solve TSP problems. Here is my code library(TSP) concordePath = "E:/Concorde_Code/" concorde_path(concordePath) concorde_help() dataset_path = "E:/RA/" name = "graph1.txt" dataset =…
Sarwan Ali
  • 151
  • 1
  • 1
  • 11
1
2