Is Dijkstra's overrated????

Правка en1, от Victor_Luis123, 2024-01-09 04:54:54

Recently I got accepted on the Shortest Routes I problem from the CSES problemset using the Bellman-Ford algorithm. If you don't know what relaxation means in this context or what the pseudocode of the Bellman-Ford algorithm looks like you can study the algorithm before continuing the reading.

Here's my idea for solving the problem

Firstly, I applied the typical optimization when all the edge weights in the given graph are positive, which involves stopping the algorithm once no relaxation operation occurs during an iteration. After getting TLE in 6 cases I thought in a way of ordering the edges in order to take advantage of the latter optimization. Finally, I deleted multi-edges(storing just the lowest weight of the repeted edges) and in a very intuitive manner I run a BFS from the source( node 1 in this case) and I sorted the edges in the same order the BFS had visited them (including back edges). Surprisingly, It passed the tests!!!!

I'm wondering if someone could be so gentle of hacking my solution or explain me why it works. I don't know how to filter by name in the hacking page of the CSES website in a certain problem, however, you can find my submission if you go to the hacking tab in the Shortest Routes I problem and then sort by maximum runnung time, my submission shows up in the 4th page with a max runtime of 0.95 seconds with the username Victor_Luis123. Thanks in advance.

Теги weighted graph, bellman ford, dijkstra, amazing

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Victor_Luis123 2024-01-09 07:39:51 9 Tiny change: ' like you can study the' -> ' like you should study the'
en1 Английский Victor_Luis123 2024-01-09 04:54:54 1668 Initial revision (published)