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

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

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
  • Проголосовать: не нравится

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +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).

→ Ответить
  • »
    »
    9 лет назад, скрыть # ^ |
    ← 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?

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

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

→ Ответить