hamiltonian cycle python wrong answer

Question

given n as number of nodes and edges as a list of edges

can anyone tell me whats wrong with my code. It works on some instances but doesnt work for all of them

for edgeindex in range(len(edges)):
    alltrue = [True]*(n)
    visited = [False]*(n)
    S = []
    start = edges[edgeindex][1]
    visited[start] = True
     S.append(start)
     nex = start
     for edgeindex2 in edges[edgeindex:]:
         if edgeindex2[0] != nex:
             continue
         if visited[edgeindex2[1]] == False:
             visited[edgeindex2[1]] = True
             S.append(edgeindex2[1])
             nex = edgeindex2[1]
         if visited == alltrue:
             return 'yes'
return 'no'

Answer 1

Your code is a greedy approach, and add the next edge it can travel to - to your path. However, this greedy approach does not work for the Hamiltonian Path Problem (which is NP-Complete, so there is no known 'efficient' solution to it...)

Failing example:

G = (V,E), V = {1,2,3}, E = {(1,3),(1,2),(2,3)}

Now, assume you are starting from 1, and travel first through (1,3). At this point you are done, and you cannot find a Hamiltonian Path. However, the path 1->2->3 exists and you won't find it.

Solution:

The simplest way to solve Hamiltonian Path is to generate all possible permutations, and check if any of them forms a Hamiltonian Path. There are more efficient (and complicated) solutions - but they too require exponential running time.