Zur Mindestkantenregel:

Das Ziel, bei der begrenzten Enumeration möglichst frühzeitig die Berechnung abbrechen zu können, wird dadurch verbessert, dass man nicht die Gesamtlänge der Kanten, sondern nur ihre Abweichungen, d.h. die Differenz von der kleinsten Kantenlänge betrachtet. Üblicherweise wird dazu jeder Zahlenwert der Ausgangsmatrix um die kleinste Kantenlänge aller Kanten reduziert.

Will man die Ausgangsmatrix nicht verändern, kann man auch bei jedem Zwischenergebnis für die noch ausstehenden Kanten jeweils die kleinste Kantenlänge hinzuzählen und erst dann das Ergebnis mit dem bereits früher gefundenen kleinsten Teilgraphen vergleichen. Ist das Ergebnis größer als dieser Teilgraph, dann kann an dieser Stelle die Berechnung abgebrochen werden. Im Beispiel ist die kleinste Kantenlänge 220 km lang, so dass für jede noch ausstehende Kante dieser Mindestwert hinzugerechnet werden kann.

Nachdem jetzt bei der hier vorgestellten Lösung jedem Kantenplatz die relevanten Kanten zugeordnet werden können, muss die minimale Kantenlänge nur noch aus diesen Kanten und nicht mehr aus allen Kanten ermittelt werden. Es werden also in diesem Beispiel nicht mehr generell für jede ausstehende Kante 220 km sondern individuell für jeden einzelnen Kantenplatz der Mindestwert der dort möglichen Kanten berücksichtigt. Dieser Wert ist zumindest für die wichtigen ersten Kantenplätze höher. 

Beide o.a. Verfahren zur Ermittlung des abzuziehenden Wertes sind "mit Zurücklegen". Besser sind Verfahren "ohne Zurücklegen", denn jede Kante kann zwar ggf. an mehreren Kantenplätzen stehen, innerhalb eines Teilgraphen jedoch immer nur an einem Platz. Ohne Zurücklegen und ohne Berücksichtigung des Kantenplatzes ist die Ermittlung des abzuziehenden Wertes einfach: Man zählt für jede noch ausstehende Kante die jeweils kleinsten Kantenlängen aller Knoten zusammen: 220 + 256 + 280 + 297 + 305 + 312 + 337 + 367 + 371+ 383 + 407+ 409 ........

Ohne Zurücklegen aber mit Berücksichtigung des Kantenplatzes (und damit implizit auch mit Berücksichtigung der Reihenfolgeregel, dass die Folgekante immer mit einer größeren Knoten-Nr. beginnen  muss) wird die bisher einfache Berechnung schwieriger. Der abzuziehende Wert muss für jeden Kantenplatz aus den kleinsten Kanten der noch ausstehenden Kantenplätzen getrennt berechnet werden. 

Diese ggf. manuell durchzuführende Berechnung bringt schon gute Werte Der optimalen Wert je Kantenplatz läßt sich in diesem Beispiel aber nur maschinell berechnen, weil bei der Berechnung nicht nur Kanten mit der kleinsten Kantenlängen je Knoten zu berücksichtigen sind.