Speeding up my Advent of Code solution with Dijkstra's Algorithm

Re:Speeding up my Advent of Code solution with Dijkstra's Al... by OskarS on Saturday January 01, 2022 @07:15AM (#29757693)

That assumes that the path only ever goes right and down. There’s no basis for that assumption in the general case, it’s entirely possible that the shortest path has to take a “detour” to avoid some high cost sections. This is a shortest-path problem, not a DP problem.

[ Parent | on HN ]

Re:Speeding up my Advent of Code solution with Dijkstra's Al... by Kwantuum on Saturday January 01, 2022 @08:45AM (#29758209)

And in fact, there were detours in pretty much all the solutions I've seen posted online for part 2

[ Parent | on HN ]

Re:Speeding up my Advent of Code solution with Dijkstra's Al... by n4r9 on Saturday January 01, 2022 @07:44AM (#29757850)

Ah, I see what you mean. The shortest path could snake around a lot. Not quite as easy as I thought!

[ Parent | on HN ]

Re:Speeding up my Advent of Code solution with Dijkstra's Al... by jacobmischka on Saturday January 01, 2022 @08:01AM (#29757950)

Yep, I wasted a few hours trying to force the DP solution to work as well before giving up and just using Dijkstra.

[ Parent | on HN ]