Enter Route Data
Example Data Table
| From | To | Distance |
|---|---|---|
| A | B | 12 |
| A | C | 10 |
| A | D | 19 |
| A | E | 8 |
| B | C | 3 |
| B | D | 7 |
| B | E | 6 |
| C | D | 2 |
| C | E | 20 |
| D | E | 4 |
Formula Used
The cheapest link algorithm is a greedy method for building a Hamiltonian circuit. It sorts all available edges from the smallest cost to the largest cost. It then accepts an edge only when both endpoints still have degree less than two. It also rejects any edge that creates a smaller closed circuit before all vertices are included.
Total route cost = sum of all accepted edge costs.
Decision rule: choose the lowest available valid edge, avoid degree violations, and avoid premature cycles.
How to Use This Calculator
Enter every vertex name in the vertices field. Then add each weighted edge on a separate line.
Use the format A,B,12 for an edge between A and B with cost 12.
Press the calculate button. The result appears above the form and below the header.
Review accepted edges, rejected edges, reasons, total cost, and route order.
Use the CSV or PDF buttons to save the result for classwork, reports, or route planning notes.
Cheapest Link Algorithm Guide
What the Method Does
The cheapest link algorithm helps build a low cost tour through several points. It is often used while studying Hamiltonian circuits and traveling salesman problems. The method is greedy. That means it makes the best local choice at each step. It does not test every possible route. Instead, it reviews edges from lowest cost to highest cost.
Why the Rules Matter
A route must visit each vertex once before returning to the start. Therefore, each vertex can connect with only two selected edges. One edge brings the tour into the vertex. Another edge takes the tour out. If a vertex receives three edges, the path is invalid. The calculator blocks that mistake automatically.
Cycle Control
A smaller cycle is another common issue. For example, three cities may form a closed loop too early. That loop cannot include the remaining cities. The calculator checks whether a new edge closes a circuit before the final step. If it does, the edge is rejected. The final edge is allowed only when it completes the full route.
Reading the Result
The result table shows each edge in sorted order. It also shows whether the edge was accepted or rejected. The reason column explains the decision. This makes the tool useful for learning. You can follow each step and compare it with manual work. The accepted edge table shows the final greedy selection.
Best Use Cases
Use this calculator for classroom problems, route examples, network exercises, and graph theory practice. It is helpful when many edge choices are available. It also reduces arithmetic errors. Remember that the cheapest link method gives a greedy answer. It may not always give the absolute best possible tour. Still, it is fast, clear, and easy to explain.
FAQs
What is the cheapest link algorithm?
It is a greedy graph method that selects the lowest cost valid edges to form a Hamiltonian circuit.
Does this calculator find the perfect shortest route?
Not always. The cheapest link method is greedy, so it may miss the absolute optimal route in some graphs.
What input format should I use?
Enter vertices as names separated by commas. Enter each edge as Start, End, Cost on its own line.
Can I use decimal costs?
Yes. The calculator accepts decimal costs, including distances, prices, travel times, or weighted scores.
Why was an edge rejected?
An edge is rejected if it gives a vertex more than two edges or creates a smaller circuit too early.
What is a Hamiltonian circuit?
It is a closed route that visits every vertex exactly once before returning to the starting vertex.
Can I download the result?
Yes. Use the CSV button for spreadsheet data or the PDF button for a simple report.
How many vertices can I enter?
You can enter many vertices, but very large graphs may be harder to review in the result table.