Mikel_Arteta_8's blog

By Mikel_Arteta_8, history, 2 years ago, In English,
Hi!

Many of you may have heard about shortest path problems of unweighted graph problems which are solved by 'meet in the middle' technique (MITM), and also solved them. My teacher taught me the implementation, but understanding it correctly hadn't been easy for me, until now. I also tried to modify my teacher's implementation in a clean way, and it worked (at least it helped me get accepted solutions), which made me feel excited.

So i'm writing this blog to share with you my implementation and how does it work, because i believe that some of you might be also having problem in understanding and implementing it, and what i'm writing could help you. I will write everything based on my experience, so there might be some mistakes, but i'm trying my best.

Introduction

Simple MITM Problem

Unweigthed graph problems

Now we have more interesting problems. They are unweighted graph problems.

Problem
  • For a permutation p 1, p 2, ..., p n of n integer from 1 to n (1 ≤ n ≤ 10). You can swap two consecutive elements p i and p i + 1 (1 ≤ i < n). Find minimum number of swaps to change p to another permutation p' = p'1, p'2, ..., p' n.

Seem like there is nothing related to graph in the statement. But let's see: Assume one permutation is one vertex, then every swaps of a permutation's elements is an edges which connect this vertex with another vertex. So finding minimum number of swaps now becomes a simple BFS/shortest path problem.

Now let's analyze time complexity. We have n! vertices, each vertex has n - 1 adjacent vertices. We also have to store vertices's visited state by map, because their representations are hard to be stored by normal arrays. So total time complexity is o(nlog(n!) × n!). Of course, this complexity can not pass 1 second time limit. That why we need MITM technique to make the solution faster.

MITM solution

Let's remember the BFS algorithm to find shortest distance of a path start from vertex start to vertex finish:

  • Push start into queue's back, visited start = true, let root = start.

  • Let D u be the shortest distance from root to vertex u, D root = 0,.

  • While queue is not empty, pop queue's front which is vertex u, then push all vertices v which are adjacent with u and haven't visited yet (visited v = false) into queue's back, then let D v = D u + 1 and visited v = true.

  • Result = D finish.

MITM solution is similar to BFS solution. Below is my implementation:

  • Let both start and finish be roots. We BFS on 2 roots start and finish at the same time, but using only one queue.

  • Push start and finish into queue's back, visited start = visited finish = true.

  • Let src u be the root of vertex u in BFS progression. So src start = start and src finish = finish.

  • Let D u be the shortest distance from vertex u to it's tree's root. So D start = D finish = 0.

  • While queue is not empty, pop queue's front which is vertex u, then push all vertices v which are adjacent with u and haven't visited yet (visited v = false) into queue's back, then let D v = D u + 1, src v = src u and visited v = true. Especially, if v was visited and then we can immediately return Result = D u + D v + 1.

Instead of pushing only start vertex into queue at first, we push both start and finish into queue. That means we will go from start and finish at the same time. It's like we BFS with 2 different trees, but using the same queue, not 2 separate queues at the same time. Also for each vertex u, we know which is it's root, and shortest distance from root to it ( src u and D u).

Then for a vertex u in front of queue, if there is an adjacent vertex v which has different root (assume it is finish) of u's root, which means they were from different BFS trees, then we return result = D u + D v + 1.

So with BFS you have to travel in a tree with depth = S to find the anwser, now you just have to travel in two trees with smaller depths, later we will prove that the smaller depth is about . It sounds like MITM!

But there is one thing that made me confused: Shortest path from start to u + shortest path from finish to v may be not equals shortest path from start to finish (let's ignore 1 of the formula), so why can we return the anwser immediately when we meet a pair (u, v) like above? It took me a long time to find the anwser.

My proof

See the description of the queue below:

  • S i is set of vetices which have shortest distance from root start equals i.

  • F i is set of vetices which have shortest distance from root finish equals i.

  • Sets are placed in chronology order. Set which is placed before another set means the vertices of that set were pushed into queue earlier.

  • Sets have red color means their vertices were poped out of the queue.

  • Set has yellow color means there is one vertex belong to that set being in front of queue and being processed. Of course there is only one set which has yellow color.

  • Sets have green color means their vertices were pushed into queue and are waiting to be processed.

There is one property that you need to remember:

  • When a vertex u are in front of queue, the maximum possible D v which v has been pushed into queue is  ≤ D u + 1 (1).

Okay. Now we are going to find out why we can return the answer like what i said in my implementation. Let u be the vertex in front of queue (being processed), S is the length of shortest path, and v is the ajdacent vertex which has different root of u's root.

  • If there is one shortest path with length 4 (even) then we get the queue state like this:

  • If the shortest path has length 5 (odd) then we get another queue state:

In both cases, and , so D u ≤ D v.

Now, if there were a vertex u' which D u' < D u (be pushed into queue earlier), and has an ajdacent vertex v' which was visited, has different root and D u' + D v' + 1 = S, then D v' > D v. So D v' - D u' ≥ D v + 1 - (D u - 1) = D v - D u + 2 ≥ 2, then D v' ≥ D u' + 2. That is wrong because of property (1).

So we can prove two things:

  • We can immediately return the answer at the first time we meet a satisfied pair (u, v).

  • If shortest length is S then and , then the depths of two BFS trees of MITM technique is about .

Pseudo code for my implementation:

visited[start] = visited[finish] = true;
D[start] = D[finish] = 0;
src[start] = start; src[finish] = finish;
queue.push(start); queue.push(finish);
while (!queue.empty()) {
    vertex u = queue.front(); queue.pop();
    for (vertex v: adjacent(u)) {
        if (!visited[v]) {
            visited[v] = true;
            src[v] = src[u];
            D[v] = D[u] + 1;
            queue.push(v);
        } else if (src[u] != src[v]) return D[u] + D[v] + 1;
    }
}

Now it's easy to implement it. Notice that instead of using visited and D, you can use just only D to do both by assiging D start = D finish = 1. Of course we need to adjust the returned result.

Here is one problem which can solve by MITM technique. Everything is similar, except finding adjacent vertices, which is a little bit complex. It can also be solve by simple BFS, so you can do both to compare their run times. In case you need my implementation,

here is it

by the way,

need a rest?
Extended problem

The above problem is simply find shortest path between to vertices in graph. The next problem is also finding shortest path, but has a few differences:

  • For a graph G with n vertices numbered from 1 to n, m edges and set S of k source vetices S 1, S 2, ..., S k (1 ≤ S i ≤ n). Find a shortest path with different start and finish vertices, and those vertices are belong to S.

Firstly we push all source vertices into queue, set each of their src equals themself. After that we will do everything like the implementation we did. The proving is similar to what i did above.

The end

That is everything i want to share with you. I tried my best to help you understand the idea of my implementation and how does it work. Again, my knowledge is limited, so i may missed something, or made some mistakes in this blog.

Thanks for reading!

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

»
2 years ago, # |
  Vote: I like it -52 Vote: I do not like it

Random theory + dead meme = upvote...

You think it's easy don't you?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    I put a lot of effort into it because i think it could be useful for everyone. I also find it's hard to find the implementation of this kind of problem on the internet, so i decided to write one. If you just read a few word then judge it, then i think you should read it carefully again.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I mean you think it's easy to get upvote. But damn this kid get triggered.

»
2 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

Nice trick & nice implementation , i had read this somewhere but never tried to implement or prove it formally . In your extended problem , we can just add a virtual vertex(V) and add edges from it to those K vertices with an edge cost of 0 ,and find the shortest path from this V to the destination vertex (this is a pretty classic trick ) finally subtract 1 from answer and return it , of course the working of the algorithm is the same as your's after first step but instead of thinking multiple source bfs it is easy to think of it as like single source bfs .

  • »
    »
    23 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think you might have misunderstood the problem. Or I might have misunderstood what you said.

    In the extended problem, the destination vertex has to be one of vertices of the given set S. There is no fixed destination. So if you add a virtual vertex V and add edges from V to all the nodes in S, then how do you get the final solution since all of your destinations have a distance equal to 1?

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

      we create a virtual vertex and connect it to those K source vertices with edge costs of 0, and run dijkstra from this virtual vertex . then finally we get shortest distance from virtual source to each and every vertex , if we observe then every shortest path passes has first immediate vertex a source vertex(one of the K source vertices ) so this is like shortest distance from one of the K- source vertex to any other vertex . so just check the minimum distance to reach from virtual source vertex to all of the destination vertices and that should be the answer. If i said anything wrong ping me.

»
23 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Isn't the problem solvable in NlogN? Compose the 2 permutations and find the number of inversions? (as it's known the number of inversions is the minimum number of swaps to get from 1 2 ... N to a given permutation). Also it's pretty easy to prove: assume you go from p to 1 2 .. N for simplicity. Every step decreases the number of inversions by at most 1, so the number of inversions is a lower bound. On the other hand, always swapping positions i so that p[i] > p[i + 1] (which for sure exist if we haven't reached the destination) is a valid strategy, so that's the answer.

  • »
    »
    23 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Yes, this version of the problem is very easily solvable by what you described, but the above technique can be more generalised. For example, if there is some cost function on swapping every two elements, which may not satisfy triangle inequality, then it's hard to come up with a solution similar to finding inversions. The above solution, however can be easily extended.

    Apologies if I said something wrong.

»
23 months ago, # |
  Vote: I like it -8 Vote: I do not like it

how to become khung like you? please teach me

»
23 months ago, # |
  Vote: I like it +13 Vote: I do not like it

This is exactly "extended problem": 100812G - Short Path

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thankyou....very beautifully written.