Victor_Luis123's blog

Is Dijkstra's overrated????
By Victor_Luis123, history, 11 months ago, In English

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 should 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.

  • Vote: I like it
  • +16
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Auto comment: topic has been updated by Victor_Luis123 (previous revision, new revision, compare).

→ Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

The time complexity of Bellman-Ford might be too big if we iterate over edges, again and again, multiple times. So, we can ask the question, when do we need to iterate it over and over again? The answer is simple, let's consider some path from the vertex s to the vertex t. Let's say that this path is the shortest for these two vertices. We need to iterate over all edges one more time, if there is some vertex x and the path (x -> t) will be considered before the path (s -> x). It is very familiar to this problem: CSES — Collecting Numbers. So, Bellman-Ford works slow, if there are lots of 'edge inversions'.

Your solution sorts the edges and the edges that are closer to the starting vertex will be considered first. So, 'edge inversions' will be eliminated after such rearranging. This is what I understood from your code. If I made some mistakes, I am sorry.

Also, This solution will work slow if we have edges with negative weights.

(s -> x) is the path from s to x.

→ Reply
»
11 months ago, # |
  Vote: I like it +42 Vote: I do not like it

"Bad graph": Line of n-1 vertices (2, 3, ..., n) and edge weights of 1 between them. Then add an edge from 1 to every even node with weight 10^9. Then add an edge from 1 to 2 with weight 1.

Graph
Generator source code

Your code needs 8 seconds on my computer to solve this graph.

→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Well, Im still waiting for the response in my computer. Thanks a lot

    → Reply
»
11 months ago, # |
  Vote: I like it +49 Vote: I do not like it

A few users were hacked: https://i.imgur.com/J8AD55f.png

→ Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

There is an improvement for Bellman-Ford algorithm called SPFA (shortest path faster algorithm), aka Bellman-Ford with queue. It maintains the queue of nodes, takes node $$$v$$$ from the front, tries to improve distances to it's neighbours $$$v \Rightarrow h$$$, and if it succeeded, adds $$$h$$$ to the end of the queue if it wasn't in it. With the heuristic of swapping several first and last nodes in queue (check MAGIC stuff in my code), it passes the tests in $$$0.17s$$$.

Code.

→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thank you, I have learned something new. And by the way, I really like your way of implementing in C++.

    → Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    Bad graph for SPFA: Line of n-1 vertices (2, 3, ..., n) and edge weights of 1 between them. Then add an edge from 1 to every node i with weight 2i. (Add the edges with larger weights first).

    Graph
    Generator source code

    Your code needs 12 seconds on my computer to solve this graph. Your code without "MAGIC" needs 45 seconds on my computer to solve this graph.

    → Reply
    • »
      »
      »
      11 months ago, # ^ |
      ← Rev. 3   Vote: I like it +13 Vote: I do not like it

      I have submitted a solution using the SPFA algorithm and it got hacked in CSES with your testcases. Thanks for providing it.

      → Reply
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Added sorting of edges in non-decreasing order of weights — passed all tests in $$$0.18s$$$.

      Code.

      $$$ $$$

      Meme
      → Reply
      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        Split the edges into two edges to force the bad order:

        Graph
        Generator

        Your code needs 3 seconds.

        → Reply
        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it +14 Vote: I do not like it

          Shuffle edges instead of sorting — $$$0.17s$$$ and your case works fast.

          Code.

          → Reply