Mathematics of Graphs: Finding Hamiltonian Circuit in a Weighted Graph
A method of finding a Hamiltonian circuit in a complete weighted graph is given by the following greedy algorithm:
• Choose a vertex to start at, then travel along the connected edge that has the smallest weight. (If two or more edges have the same weight, pick any one.)
• After arriving at the next vertex, travel along the edge of smallest weight that connects to a vertex not yet visited. Continue this process until you have visited all vertices.
• Return to the starting vertex.
The greedy algorithm attempts to give a circuit of minimal total weight, although it does not always succeed.
