Блог пользователя JonTyrell

Djikstra + Bitwise OR
Автор JonTyrell, история, 7 лет назад, По-английски

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 ?

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    7 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

    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?

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

        → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

      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.

      → Ответить
»
7 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

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

→ Ответить