Kashish Dugar

Dijkstra, try two

On Tuesday I got tangled up in Dijkstra’s tables. Today I learned to think of them as price tags.

If a bus costs ₹2 and then a train costs ₹3, the whole trip costs ₹5. A price tag on a place is the whole trip total from Start, not just the last road.

First I listed every route on the book’s map. I predicted that a route with more roads would cost more. I was wrong! Start → B → A → Finish uses three roads and costs only ₹6, which is cheaper than the two-road routes (₹7).

Then I tried a brand-new map with price tags. The rule is: always walk from the cheapest place you haven’t walked from yet, and only change a tag if you find a cheaper total. The cheapest trip was Start → A → B → C → Finish for ₹6. When I just listed routes, the best one I found was ₹8.

Electricity

I lit a blue LED with my micro:bit battery pack. Pulling one leg in and out made it flash on and off. That’s what a telegraph key is: a switch.

A long straw is harder to drink through than a short one. A long wire is the same for electricity. It’s called resistance.

Then I built a push-button circuit on a breadboard. It didn’t work! I traced it row by row and found both LED legs were in row 15. A row is like one wire, so the electricity skipped the LED. After I moved one leg, the LED was on while I held the button.

My Dream Smoothie

Petzold’s Chapter 8 has a “Dream Kitty” control panel. Cats didn’t make sense to me, so I made a Dream Smoothie panel instead. My rule is Blueberry AND (Strawberry OR Banana) AND Chocolate granola.

AND switches go in a line and OR switches go side by side. My first drawings had a shortcut back to the battery, so the bulb got skipped, just like the LED in row 15. I crossed out the wrong wires until it was one loop.

Afternoon

In the afternoon I worked on my one mistake: writing a single road’s price instead of the whole trip. Before every tag I said a sentence: “₹__ to reach , plus ₹ for the road, equals ₹__.”

Listing every route is a real algorithm called brute force. But my big map had 12 routes! Price tags are faster. On the big map the cheapest trip was Start → A → B → D → Finish for ₹8.

Then I tried a new map on my own. Every tag was a whole-trip total, not a road. But I used A’s old tag (3) instead of its new one (2), so I got 6 instead of 5. I fixed it: Finish = ₹5. Next time I’ll use the newest tag the first time.

What’s next

One more fresh map with price tags, then I build Dijkstra in code.