Kashish Dugar

I had a cold today, so it was a harder morning.

Preorder and postorder

I already had inorder (left, node, right). Today I added two more:

I predicted both on paper first. When I ran it, preorder printed 5, 8, 3, 1. That was wrong! I had put right before left. I only found the bug because I had my prediction to compare with.

Dijkstra’s algorithm

BFS finds the path with the fewest steps, but fewest steps is not always cheapest. Dijkstra’s algorithm finds the cheapest path when roads have different costs.

You keep two tables: costs (how much it costs to get there from Start) and parents (where you came from). You always process the cheapest place next. Once it’s processed, its cost is final.

With help, I worked through the book’s example and the cheapest path was 6: Start → B → A → Finish.

Then I tried to fill the tables again on my own. It did not go well:

My first try

I wrote Finish = 1, but that’s only the last road, not the total from Start.

My second try

My second try got even more tangled. I’ll try again tomorrow with a clearer head.

Negative roads break Dijkstra: a road of −10 could make a place cheaper after it was already locked in.

BFS from memory

Yesterday my BFS looked a lot like the book’s. Today I closed the book and wrote it again in a new file. I only peeked once, very quickly, to check the function names. It found Rumi again.

What’s next

Dijkstra tables again, then building Dijkstra in code.