graphs – How to optimally traverse all the vertices of the graph?


What algorithm can be used to find the shortest (with min the sum of the weights of the arcs) path passing through all the vertices of the graph?

Will Dijkstra's algorithm work ?


This is a problem of finding a Hamiltonian path, and it is NP-complete. If you need an accurate algorithm with a small (maximum in the region of 20-25) number of vertices, then there is a solution using dynamic programming that works faster than brute force:

With a larger number of vertices, the problem is already solved by approximate (greed, "ants") algorithms:

Scroll to Top