wish_me's blog

BFS with multiple sources
By wish_me, history, 5 years ago, In English

Can any one explain the topic and also tell me the list of some good problems.Thanks in advance.

 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://www.codechef.com/SNCKPB17/problems/SNSOCIAL/

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Concept : You push all the cells/nodes/vertices which are the so called "Source" / Starting Vertices in a queue. In these types of problems you generally have to find the shortest Distance/Cost of reaching all the vertices.

After pushing all the source vertices into the queue(priority queue/set) and performing the usual Djikstra you get your desired answer.

This works in the usual time limit if the total number of nodes and edges are not more than say ~2e5

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good beginner level problem related to this topic- http://www.spoj.com/problems/BITMAP/

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

http://codeforces.com/contest/1283/problem/D

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

https://codeforces.com/contest/1272/problem/E

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

Another way to think about multiple sources that's potentially nicer to code is to add a fake source with edges to all the real sources, then BFS as normal, then subtract 1 from all the distances.

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the implementation trick!!!

    → Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you please elaborate what are you trying to tell ?

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

      Imagine this is your original graph (not including the red node/edges), and A, B, C are your multiple sources. We can create an additional node X and the red edges shown, then do a standard BFS starting from X. Finally, all the distances will be 1 more than they should be, because you had the extra hop from X to the real source at the beginning of each path.

      → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it
      • Instead of pushing all the real sources into the queue, you add a fake source, link it to all the real sources, and just push that single fake source into the queue.
      • If you do the BFS, it will take the fake source out of the queue first, and then it will push all the real sources into the queue right after (because you link the real sources directly to the fake source, they will be the closest to the fake source, which means they should be in the queue after the fake source is visited).
      • Now, all the real sources are inside the queue, as expected. The side effect is that the calculated distances are all +1 compared to the actual distances, that's because the fake source and the fake edges increase the distance. So, subtract 1 from all the distances, and you are good to go.
      → Reply
      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sir, how does it affects the time complexity? does it make any difference at all.

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

          I think there should be no huge differences. As our red coder said above, it's just nicer to code, as traditionally, you start with a single vertex only.

          If I misunderstand anything, please tell me.

          → Reply
          • »
            »
            »
            »
            »
            »
            17 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yes, I also see that it doesn't affect the time complexity to a great extent.

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

Another Problem: 986A - Fair

Add all the nodes you want to BFS from into the initial queue and run it.

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is another one!

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://usaco.guide/gold/bfs

Theory + 11 questions to practice from various OJs

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://www.spoj.com/problems/AKBAR/

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

I love this community. Thanks for various approaches on multi source BFS.

→ Reply