I made a greedy algorithm that solves minimum-weighted-Hamiltonian-circuit problem.The algorithm always picks the cheapest edge,if there is no way to find the circuit from the current edges set then the algorithm drops the last edge and picks the next cheapest.I'm not sure about the complexity of this algorithm,can someone explain it to me Here is the pseudocode
HC(currentVertex,expandedVertices,path,sum,N)
if size(expandedVertices)==N then
print(path)
return sum
end if
expandedVertices.add(currentVertex)
vertices=getAdjacentNodes(expandedVertices)
sort(vertices)
for i=1 to size(vertices) do
path.append(vertices[i])
cost=HC(vertices[i],expandedVertices,path,sum+getEdgeCost(currentVertex,
vertices[i]),N)
if(cost>0) then
break
end if
path.remove(vertices[i])
expandedVertices.remove(currentVertex)
return cost
Your algorithm uses brute force to find a path, so the maximum running time is
O(n!)
(for a fully connected graph). There might only be one possible route, the last one you check.In most real-world cases, this algorithm will be faster. The problem is usually referenced to by its other name: the traveling salesman problem. Wikipedia has a list of good algorithms and heuristics that are faster than yours.