Speaking of recent breakthroughs to classic graph algorithms, there's one from 2021 that I find amusing.

It's about the metric Traveling Salesman Problem (TSP). Since it is NP-hard, it's unlikely a polynomial-time algorithm exists. So, the question is, what's the best approximation ratio we can achieve in polynomial time? The best known approximation ratio stood at 1.5 since 1976, thanks to Christofides' algorithm (tours found by Christofides' algorithm are at most 50% longer than the optimal length).

After so many years without improvement, it was believed to be optimal.

Then, after 45 years, the approximation ratio was improved from 1.5 to... 1.5 − 10^(−36)

Paper title: "A (slightly) improved approximation algorithm for metric TSP" 😂😂

Fun fact: the Dijkstra improvement paper won the 2025 best paper award at FOCS, a top CS theory conference. This TSP paper won the 2021 best paper award at that same conference.