UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 17.3 Free with a free account
Cheapest Routes in a Weighted Network
Data Structures and Algorithms · Chapter 17: Graphs and MemorySection 17.3 · lesson 80 of 87video coming soon
← How Different Connection Types Change a NetworkNext lesson: Graphs Through the Lens of Discrete Mathematics →
In this lesson
How Dijkstra's algorithm finds the cheapest route from one source.
- Explain why the fewest edges is not always the cheapest route in a weighted network
- Trace Dijkstra's algorithm with relaxation, a priority queue, and lazy deletion
- Rebuild a cheapest route from predecessor links
- Explain Dijkstra's running time and why negative edge costs break it
Free study notes
Get this lesson's notes by email
The key points and 4 practice questions with answers, in your inbox. One email, free.
One email. Unsubscribe in one click.
Transcript
Everything said in the video, section by section (1,876 words). Read along, or search it.
Opening Question
The Quickest Way Across Town
A driver asks a map app for the quickest way across town. The app doesn't count streets or turns. Every road has a travel time, and the answer is the route whose times add up to the smallest total. Four short roads can easily beat two long ones. So how does the app find the cheapest total, without trying every possible route?
Definition
Weighted Networks and Shortest Paths
Here's a small network of six places, A to F. Every road works both ways, and the numbers are the costs: minutes, kilometers, or prices. The method is the same. A network whose roads carry numbers is a weighted network. The numbers are its weights, and asking for the cheapest way from here to there is the shortest-path problem.
Fewest Roads
Why Breadth-First Search Falls Short
Say we want to go from A to E. Breadth-first search, from lesson ten point five, counts roads. It picks A, F, E: only two roads. But the first road costs fourteen, so the total is fourteen plus nine: twenty-three. The detour through C uses three roads: nine, then two, then nine. That's twenty, cheaper, even with more roads. Fewest roads is the right answer only when every road counts the same. Once the costs differ, we need a new method: Dijkstra's algorithm.
Relaxation
Lowering an Estimate Through a Cheaper Way In
Dijkstra's algorithm works from one starting place, the source, and finds the cheapest cost to every other place. Throughout, every road cost is zero or more. For every vertex v it keeps an estimate, dist of v: the cheapest cost found so far. At the start, that's zero for the source and infinity for everyone else. An estimate is always the cost of a route that really exists. So it's never too low. It can only be too high, because a cheaper route may not have been found yet. The step that lowers an estimate is called relaxation. Take a road from u to v with cost w. Going to u, and then along the road, costs dist of u plus w. If that's less than dist of v, we've found a cheaper way in. Set dist of v to the new value, and remember that u comes just before v. Otherwise, nothing changes. Here's relaxation on one road. C has been finished at nine. The road from C to F costs two, and F's estimate is fourteen. Nine plus two is eleven, which beats fourteen. So F drops to eleven, and C is remembered as the place before F. Now the same road the other way: C's estimate is nine, and F to C would give eleven plus two, thirteen. Thirteen is worse than nine, so nothing happens.
Bookkeeping
Predecessors, Settled Flags, and a Queue
Besides the estimates, the algorithm keeps three more things. prev of v: the vertex just before v on the cheapest route found so far. It starts at minus one, meaning none. done of v: true once dist of v is final. The vertex is then called settled. And a priority queue of entries, each a vertex with a distance. The smallest distance always leaves first. At the start, it holds only the source, at zero.
The Algorithm
A Ripple Spreading Across a Pond
Picture a ripple spreading across a pond. It reaches near points first and far points later, and a point is finished the moment the ripple arrives. Dijkstra's algorithm is that ripple. Start with the source in the queue. Take the entry with the smallest distance. If its vertex is already settled, throw the entry away, and take the next one. Otherwise, settle the vertex: its distance is now final. Then relax every road leaving it, and each time an estimate drops, add a new entry to the queue. Repeat until the queue is empty.
Lazy Deletion
Skipping Stale Queue Entries
One detail needs care. Java's PriorityQueue can add an entry, and remove the smallest, but it can't lower the priority of an entry already inside. So when an estimate drops, the code adds a new entry, and leaves the old, more expensive one in the queue. That old entry is stale. When it finally reaches the front, its vertex has already been settled through the cheaper entry, so it's simply skipped. This habit is called lazy deletion.
Trace Part One
Settling A and Then B
Let's run it from A, on the same network, with the cost of every road written in. A leaves the queue first, at zero, and is settled. Relaxing A's roads gives B seven, C nine, and F fourteen. Three entries join the queue. The smallest now is B, at seven. Settling B, the road to D gives seven plus fifteen: twenty-two.
Trace Part Two
C Lowers F From Fourteen to Eleven
Next is C, at nine. And here's the key moment. The road from C to F offers nine plus two, eleven, which beats fourteen. So F drops to eleven, and a new entry, F at eleven, joins the queue. The old entry, F at fourteen, stays behind, stale. C also lowers D, from twenty-two to twenty, through the road costing eleven.
Trace Part Three
A Tie at Twenty and Skipped Stale Entries
F comes out at eleven and is settled. Its road to E gives eleven plus nine: E gets twenty. E and D are now tied at twenty. Either can go first, and both are settled at twenty. When the stale entries, F at fourteen, and D at twenty-two, finally come out, their vertices are already settled, so they're skipped without any work. In all, eight entries went in, and eight came out, two of them stale.
Quick Check
Closing the Road Between C and F
Quick check, on the same network. Suppose the road between C and F is closed. Everything else stays. What's the cheapest route from A to E now? A, C, D, E? A, F, E? Or A, B, D, E? Pause, and decide. This time the algorithm picks A, F, E, at fourteen plus nine: twenty-three. Without the cheap two-cost road, the detour through C has to go by D: nine, eleven, and six, which is twenty-six. And A, B, D, E costs twenty-eight. The fewest-roads route wins here, but only because of the costs, not because it has fewer roads.
Rebuilding the Route
Following Predecessor Links Backward
The distances say what a route costs, but a traveler also needs the roads. That's the job of prev. Each time relaxation lowers an estimate, it also records which vertex comes just before. At the end, the prev links form a tree, rooted at the source: the shortest-path tree. To rebuild the route to E, start at E and keep going to prev. E's prev is F, F's prev is C, and C's prev is A. That walk gives the route backward, so the code adds each vertex at the front of a list. Read forward: A, C, F, E, at a cost of twenty. One guard first. If a target was never reached, its distance is still infinity, and there's no route to report.
Correctness
Why a Settled Distance Is Final
Why is it safe to call a vertex final the moment it's settled? Suppose u is the closest vertex left in the queue, with estimate d. Could some other route reach u for less than d? Any such route starts at the source, inside the settled region. At some point it must step out, along a road to a vertex x that isn't settled. But u was the closest unsettled vertex, so x is already at least d away. The rest of the route, from x on, can only add cost, because no road costs less than zero. So the other route costs at least d, and d is final. That one argument is the whole reason the algorithm works.
Running Time
Each Road Examined Exactly Once
How much work is it? Let V be the number of vertices, and E the number of roads, counting a two-way road once in each direction. Every vertex is settled once, and a vertex's roads are looked at only when it's settled. So each road is examined exactly once: E in all. An entry is added only when a relaxation succeeds, so at most E entries ever enter the queue. Each heap operation costs time proportional to log V. Altogether, that's order of V plus E, times log V. In a test on random one-way networks with four roads per vertex, roads examined always equaled E, and only about one point three three entries were added per vertex.
Simpler Version
Plain Scanning Versus a Heap
A simpler version uses no priority queue at all. In each round it scans all V vertices for the closest unsettled one. That's V rounds of V steps: order V squared. For a network with few roads, the heap is far better. On a sparse network of three thousand vertices, the heap version was about ten times faster. But when almost every pair of vertices has a road, E is close to V squared, and the heap's extra log factor can make it the slower one. On a dense network, the plain scan won. Real road maps are sparse, which is why the heap version is the usual choice.
Limitation
A Negative Road Gives a Wrong Answer
The safety argument used one fact: the rest of a route can only add cost. A negative road breaks it. Here, S to A costs two, S to B five, A to C one, and the road from B to A is a refund of four: minus four. Dijkstra settles A at two, then C at three, through A. Only afterward is B settled at five. Now B to A gives five minus four: one, cheaper than two. But A is already settled, so its roads are never looked at again, and C keeps the value three. The true cheapest cost to C is two: S, B, A, C. The answer is wrong, and nothing reports an error. Adding a constant to every road doesn't repair it either, because routes with more roads receive more of the extra cost.
Quick Check
Fewest Steps on a Game Board
Quick check. A board game counts every move as exactly one step, and a program must find the fewest steps from one square to another. Which method fits best: breadth-first search, Dijkstra's algorithm, or neither of them? Pause, and decide. Breadth-first search. When every step costs the same, the route with the fewest steps is also the cheapest, and it needs no priority queue. Dijkstra would give the same answer. On a test network of two hundred thousand vertices, all costing one, it did, but breadth-first search was about one and a half to two times faster.
Decision Guide
Breadth-First Search or Dijkstra
So the choice is short. Every road costs the same? Use breadth-first search. Costs differ, and none is negative? Dijkstra, with a priority queue. Some costs are negative? Neither of these. Dijkstra can silently give wrong answers, so use a method built for negative costs.
Common Mistakes
Four Mistakes to Avoid
Four mistakes to avoid. First, treating the fewest roads as the cheapest. Second, adding to infinity. With Integer.MAX_VALUE standing for infinity, adding five overflows to minus two billion, one hundred forty-seven million, and change: a fake bargain. The code is safe only because it adds to a vertex just taken from the queue, which always has a real distance. Third, reading the route forward. Following prev gives it backward. And fourth, skipping the check for an unreachable target.
Key Takeaways
Dijkstra's Algorithm in Brief
To sum up. The cheapest route has the smallest total cost, which isn't always the fewest roads. Relaxation lowers an estimate when a cheaper way in appears, and records the vertex before. Dijkstra settles the closest vertex each time, skips stale entries, and runs in order of V plus E, times log V. prev rebuilds the route. And it needs every road cost to be zero or more.
About Data Structures and Algorithms at UPI Study
Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 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 All Computer Science courses Every course with PRO →
Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms
Why take it here
Why students take Data Structures and Algorithms with UPI Study
Where the credit goes
Universities that work with NCCRS
Data Structures and Algorithms 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 UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks 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 Cheapest Routes in a Weighted Network
How does Dijkstra's algorithm work?
Why doesn't Dijkstra's algorithm work with negative edge weights?
What is the time complexity of Dijkstra's algorithm?
What is lazy deletion in Dijkstra's algorithm?
About the Data Structures and Algorithms course
How many college credits is Data Structures and Algorithms?
How much does Data Structures and Algorithms cost and what is included?
Which universities accept UPI Study credits?
How long does Data Structures and Algorithms take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in Data Structures and Algorithms.
87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →