JonTyrell's blog

Djikstra + Bitwise OR
By JonTyrell, history, 7 years ago, In English

Let's say there is a directed graph with weighted edges and the distance from one vertex to another is defined as the bitwise OR of the edges in the path.Can we apply djikstra for single source shortest path here ?

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

Comments Comments (11)
| Write comment?
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Assuming each number has atmost 20 bits. Now run Dijkstra on the graph containing only 20 bits (This Dijkstra is quite different.It is min max dijkstra.So during relaxation we take max operation instead of summation) from both vertices s and t. Now remove all those edges which are not on any paths from s to t.

Now on the leftover graph run the dijkstras with 19 th bit and repeat till zeroth bit.

NOTE: Can be adapted similarly for a 32 bit number.

Do u feel this is correct??

Complexity is n logn *log(10^9).

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    Good idea to process bits from highest to lowest and consider some leftover graphs, but why Dijkstra? Even DFS will be fine. To make it clearer, here is pseudocode

    int result = 0;
    for (int bit = 60; bit >= 0; bit--) {
    if (we can reach t from s not using edges with 1<<bit lit) permanently throw edges with 1<<bit lit away
    else result += (1 << bit)

    However that is for a fixed sink. Or did you actually manage to get distances to all vertices and I just didn't understand?

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

      No, It was only for a fixed sink.Actually dfs is nice here. I had ideas of 0-1 bfs but dint want to complicate it.But I am thinking may be some sort of divide and conquer might help if we want to find for all shortest paths from a single source(Its just a intuitive feeling).

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

      what would differ if we wanted to get the maximum bitwise OR a path from s -> t?

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

        If we are allowed to repeat edges then simply take OR of all edges in this component ;p. If we are not allowed than it seems that it is at least as hard as Hamiltonian Path

        → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it -10 Vote: I do not like it

      Will this method work ? Resolve each vertex into <vertex,mask> (assuming |vertex|<10^3) and then run dfs. Now find out out the <smallest mask ,destination> which is reachable.This mask is the answer. Or I guess its more or less the same method that Swistakk gave.

      → Reply
»
7 years ago, # |
  Vote: I like it -7 Vote: I do not like it

It doesn't work considering that your distance can get smaller over time, so theoretically you have negative weights on your edges.

→ Reply