A minimum spanning tree is a useful benchmark for route problems §

Date created: 2022-07-21

When you have something like the Traveling salesman problem, you can create a “minimum spanning tree” where you calculate the shortest possible distances while assuming that backtracking is “free”.

This will show you the absolute minimum distance, and when you go back to the real problem you have a benchmark and am able to tell how close to the optimal solution you are.

---

References §

• Link to website, bibtex from Zotero or note with book/blog/etc summary