Weighted Graphs and the Traveling Salesman Problem | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 10.2 Free with a free account

Weighted Graphs and the Traveling Salesman Problem

Discrete Mathematics · Chapter 10: Graph Theory: Hamiltonian Circuits, Coloring, and RepresentationsSection 10.2 · lesson 68 of 8711 min · free with a free account

← Hamiltonian Paths and CircuitsNext lesson: Graph Coloring and Traversal →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

Finding the cheapest Hamiltonian circuit - exactly, or fast.

  • Define weighted graphs and the TSP
  • Count the distinct Hamiltonian circuits
  • Solve a small TSP by brute force
  • Apply the nearest-neighbor heuristic

Transcript

Everything said in the video, section by section (1,620 words). Read along, or search it.

Graph Theory: Hamiltonian Circuits, Coloring, and Representations

Weighted Graphs and the Traveling Salesman Problem

Section ten point one asked whether a Hamiltonian circuit exists. This section asks which one is cheapest. That's the traveling salesman problem. We'll attack it two ways: an exact method whose cost explodes, and a fast method that only promises a reasonable answer.

The Opening Problem

One Driver, Every Stop, Back to the Depot

A regional same-day parcel service sends one driver each morning to a set of drop-off zones across a metro area. The driver must return to the distribution center at the end of the run, to reload for the afternoon. From the last section, a route that visits every stop exactly once and returns home is a Hamiltonian circuit. But the dispatcher's real question goes one step further. Among all the Hamiltonian circuits on today's stops, which one costs the least in total distance, and so the least in fuel, driver time and vehicle wear? Delivery fleets, ride-share platforms and circuit-board drilling machines all face this question at scale. We'll build two contrasting methods. One is guaranteed to find the best circuit, but its cost explodes as stops are added. The other runs quickly at any scale, but only promises a reasonable circuit.

Definitions

Weighted Graphs and the TSP

A weighted graph adds a weight function to an ordinary graph. The weight function assigns a positive number to every edge, representing a cost of traversing it, like a distance, a travel time, or a price. A weighted graph is complete if every pair of distinct vertices is joined by an edge. The traveling salesman problem is normally posed on a complete graph. Why? Because the weight between two stops is taken to be the shortest road distance between them, even if no single street connects them. So every pair has a travel cost. Given a complete weighted graph with at least three vertices, the traveling salesman problem asks for the Hamiltonian circuit of minimum total weight. The weight of a circuit is the sum of the weights of its edges, including the closing edge back to the start. A minimizing circuit is called an optimal circuit.

The Running Example

A Depot and 4 Stops (km)

Here's the running example. A distribution center, D, and four drop-off stops, A, B, C and E. The table gives the road distance, in kilometers, between every pair. Take one candidate circuit: D, A, C, E, B, and back to D. Its weight is four, plus eight, plus three, plus six, plus the closing edge of seven. That's twenty-eight kilometers. It's a perfectly valid Hamiltonian circuit. But is it the cheapest? To know for sure, we need every circuit.

10.2.2

How Many Distinct Circuits?

So how many distinct Hamiltonian circuits does a complete graph on n vertices have? Arranging all n vertices in a sequence can be done in n factorial ways. But a circuit can be written starting from any of its n vertices, and all n describe the same cyclic route. Dividing by n gives n minus one factorial. And each circuit can be traveled in two directions, clockwise or counterclockwise, which describe the same undirected circuit. So divide by two. The count is n minus one factorial, over two. For five vertices, that's four factorial over two, twenty-four over two, which is twelve circuits.

Table 1

All 12 Circuits From the Depot

Here are all twelve, starting and ending at the depot, sorted from cheapest to most expensive. The optimal circuit is D, A, B, E, C, and back to D, at twenty-five kilometers. Our twenty-eight kilometer candidate ranks third, tied with another circuit. It's valid, but not the best. And only checking all twelve reveals that. Before the table is built, there's no way to know which circuit wins.

The Cost of Brute Force

Factorial Time

Brute force is correct by construction. So what does it cost? Evaluating one circuit means summing n edge weights, which is order n work. And there are n minus one factorial over two circuits. Since n times n minus one factorial is exactly n factorial, the total is theta of n factorial over two, which is theta of n factorial. Factorial time is one of the fastest-growing classes in this course. The table makes that concrete. Suppose, just for illustration, that a computer evaluates one circuit every nanosecond. Five stops take twelve nanoseconds. Ten stops, under a fifth of a millisecond. Fifteen stops, about forty-four seconds. Twenty stops take nearly two years. And twenty-five stops take nearly ten million years. Going from ten stops to twenty doesn't double the work. It multiplies it by roughly three hundred billion. Past twenty or so stops, exhaustive search is infeasible on any hardware.

Listing 1

Brute-Force TSP in Python

Here's brute force in Python. It loops over every ordering of the stops, with the depot fixed at both ends. Each time it keeps an ordering, it records the reversed ordering, so the same circuit in the other direction is skipped. For each circuit, it sums the edge weights along the route, and keeps the cheapest seen so far. Run on the delivery network, it returns D, A, B, E, C, D, with weight twenty-five, matching the table.

10.2.3

The Nearest-Neighbor Heuristic

Because brute force becomes infeasible so quickly, practical routing systems use a heuristic instead. A heuristic is a rule of thumb that produces a solution quickly, with no guarantee that it's optimal. The simplest heuristic for this problem is nearest neighbor. From the current stop, always move to the closest stop not yet visited. When every stop is visited, return to the start. From the depot, the choices are four, seven, nine and eleven. A is closest, at four. From A, B is closest, at three. From B, C at five beats E at six. From C, only E remains, at three. Then the driver returns from E to the depot, which costs eleven. The circuit is D, A, B, C, E, D, totaling twenty-six kilometers.

Figure 2

Greedy Versus Optimal

Here are the two circuits side by side. The true optimum is twenty-five kilometers, so nearest neighbor is one kilometer over. That's four percent above optimal. Close, but not exact. And the reason is visible in the trace. Nearest neighbor greedily took the cheap edge from C to E, three kilometers. That left only the expensive eleven kilometer edge to get home. The optimal circuit accepts a slightly longer middle edge, B to E at six, in exchange for a cheaper return, C to D at nine. A locally cheap choice at each step produced an expensive return trip. That's the defining weakness of greedy methods on this problem.

Speed Versus Guarantees

What Nearest Neighbor Promises

What does nearest neighbor buy, and what does it give up? Its running time is far better. At each of n steps, it scans at most n minus one unvisited stops for the minimum. That's order n squared, polynomial, which scales to thousands of stops. Its guarantee is weaker. Suppose the weights satisfy the triangle inequality, so no direct edge is ever longer than a two-edge detour through a third vertex. Ordinary road distances behave that way. Then, in nineteen seventy-seven, Rosenkrantz, Stearns and Lewis proved a bound. Nearest neighbor's tour is never more than about one half the ceiling of log base two of n, plus one half, times the optimum. They also showed the ratio really can grow with n. It grows only logarithmically, so it stays modest. But it never shrinks to zero, and no value of n guarantees the optimal circuit. The four percent gap on our example is one data point, not a general guarantee.

Listing 2

Nearest Neighbor in Python

Here's nearest neighbor in Python. It keeps a set of unvisited stops. At each step, it picks the unvisited stop with the smallest distance from the current one, adds that distance, and moves there. When no stops remain, it adds the distance back to the start, closing the circuit. On the delivery network, it returns D, A, B, C, E, D, with weight twenty-six, matching the hand trace. Notice that nothing in the loop ever looks ahead to the cost of getting home.

10.2.4

Exactness Versus Efficiency

Brute force and nearest neighbor sit at opposite ends of a trade-off that recurs throughout algorithms: exact correctness against computational feasibility. Brute force takes factorial time, and is always optimal. It's reliable only for a small number of stops, roughly twelve to fifteen, and it's used to check other methods on small instances. Nearest neighbor takes order n squared time. It isn't guaranteed optimal, though it stays within a logarithmic factor for triangle inequality distances. It scales to thousands of stops, and it's used as a fast starting point. Production routing systems typically build a circuit quickly, then refine it with local search. For example, a two-opt move swaps two edges whenever that shortens the tour, and repeats until nothing improves, or time runs out. That stays polynomial, and usually closes much of the gap, but still doesn't guarantee the true minimum. So for the dispatcher's five stops, brute force is affordable, and worth running. For a fleet with thousands of stops each morning, it's hopeless, which is why routing engines are built around fast approximate methods.

Takeaways

Exact or Fast - Rarely Both

To summarize. The traveling salesman problem turns ten point one's existence question into an optimization question: which Hamiltonian circuit costs the least? A complete graph on n vertices has n minus one factorial over two distinct circuits, once rotations and reversals are treated as the same. Brute force checks every one, so it's always correct, but factorial time makes it infeasible beyond roughly a dozen stops. Nearest neighbor runs in order n squared time by always moving to the closest unvisited stop. But it isn't guaranteed to find the optimum. Here's something to think about. Kruskal's algorithm for a minimum spanning tree also makes a greedy, locally cheapest choice at each step. Yet it's provably optimal every time. Nearest neighbor is greedy too, and it can miss the optimum. What structural difference lets greedy succeed in one problem and not the other? Think about what freedom a spanning tree has that a Hamiltonian circuit doesn't.

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Weighted Graphs and the Traveling Salesman Problem

What is the traveling salesman problem?
The traveling salesman problem asks for the Hamiltonian circuit of minimum total weight in a complete weighted graph with at least three vertices. Each edge has a positive weight, such as distance or cost. A circuit's weight is the sum of its edges, including the closing edge back to the start. The cheapest circuit is called optimal.
How many distinct Hamiltonian circuits does a complete graph with n vertices have?
A complete graph on n vertices has \frac{(n-1)!}{2} distinct Hamiltonian circuits. Start with n! orderings, divide by n because a circuit can begin at any of its vertices, then divide by 2 because each circuit can be traveled in two directions. For n=5, that gives \frac{4!}{2}=12 circuits.
How do you solve a small traveling salesman problem by brute force?
List every distinct Hamiltonian circuit, add up the edge weights of each, and choose the smallest total. With a depot and four stops there are 12 circuits to check. In the example, the best is D, A, B, E, C, D at 25 km. Since the work grows like \Theta(n!), this is practical only for roughly a dozen stops.
How does the nearest-neighbor heuristic work, and does it find the best route?
Nearest neighbor starts at a vertex, repeatedly moves to the closest unvisited vertex, and finally returns to the start. It runs in O(n^2) time but does not guarantee the optimal circuit. In the delivery example it gives D, A, B, C, E, D at 26 km, while the optimum is 25 km. Choosing cheap edges early can force an expensive return edge.

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →