4
$\begingroup$

Given a graph $G$ where loops and multiple edges are allowed. A path {$e_1, e_2, ..., e_k$} (a sequence of edges) has a cost $$ cost = e_1 | e_2 |...|e_k$$ where $|$ is the bitwise OR.

Assume for all edges in $G$, $e_i \ge 0$.

Now, the triangle inequality is satisfied, for this definition of cost. Meaning, as the path size increases, the path cost can never decrease.

So theoretically, to find the shortest between two vertices, Dijkstra's algorithm should give the right answer?

$\endgroup$
  • 4
    $\begingroup$ 1. The triangle inequality is not satisfied. "Path size increases" is not equivalent to the triangle inequality. 2. What have you tried? There's a standard proof of correctness for Dijkstra's algorithm, available in every textbook. Have you tried working through that proof, but now with the difference cost metric, to see if every step still holds? $\endgroup$ – D.W. Jun 18 '16 at 16:52
6
$\begingroup$

I'm not sure if you can adapt Dijkstra specifically in any way to this problem, but there's a different efficient solution that's actually easier to come up with.

Because bitwise operators treat bits independently, you can try to fix each bit in your answer, iteratively, from highest to lowest. The first question is "can I not have the highest bit set to 1 in my answer?". If after removing all edges with the highest bit set to 1 from the graph, the source and destination are still connected, the answer is yes, you throw away all those edges for good and proceed with the next bit. If the answer is no, you put the removed edges back, because they might come in handy, and again proceed with the next bit.

Running time is $O(Elog MaxCost)$.

$\endgroup$
4
$\begingroup$

Nice question indeed! Very interesting!!

First, let me please summarize my understanding of your problem:

Definition Let $\omega(\pi)$ denote the cost of a path $\pi\langle n_1, n_2, n_3, \ldots n_k\rangle$ which is defined as $c(n_1, n_2)|\omega(\pi')$, $\pi'$ is the suffix path $\langle n_2, n_3, \ldots, n_k\rangle$, $c(n_1,n_2)$ is the cost of the edge $\langle n_1, n_2\rangle$, and | is the bitwise or operator.

Goal To find a path $\pi^*$ from a source vertex $s$ to a target vertex $t$ such that $\omega(\pi^*)$ is minimized among all paths from $s$ to $t$.

Notice that $\omega(\cdot)$ is defined over the set of natural numbers $\mathbb{N}$. Indeed, if every vertex is characterized with $b$ bits, then the cost function takes values in the range $[0, 2^b-1]$.

Let me additionally highlight a couple of issues before going any further:

  1. Your definition of triangle inequality is not very relevant to this case. Triangle inequality is used often in relation with the behaviour of heuristics. You might instead want to mean that costs grow monotonically and, as you are interested in minimizing the cost, this notion has been recently denoted as monotonicity of state spaces by Roni Stern et al.
  2. A preferred way to verify theoretically whether Dijkstra/A$^*$ can be applied or not is to check if you are using a cost algebra or not as defined by Stefan Edelkamp et al..

Regarding the second point, if a cost distribution model satisfies a cost algebra then we know that Dijkstra/A$^*$ can be readily applied. This does not mean, however, that cost models which do not verify some properties of cost algebras can not be solved with the same algorithms ---or slightly modified versions of these algorithms.

Finally, note that you have not mentioned whether paths have to be simple or not so I will not address that issue here.

If my understanding is correct then, the cost of each edge is state-dependent: different paths to the same vertex have different costs, i.e. the cost of an edge is not a function of the out and in vertices connected through the edge (e.g., if vertices are locations over a map, then the edge cost is just the distance between them and this is a function just of the origin and target vertices of the edge), but a function of all states traversed before taking the edge!! This makes a huge difference with typical problems so that let me go deeper into this issue.

Consider the following simple digraph (i.e., no loops, no multiple edges are required to show the main difficulty in this problem):

enter image description here

where it is required to find the shortest path from 000 (in blue) to 100 (in red). Let us see how Dijkstra would work here:

  1. s is expanded and $n_1$ and $n_2$ are inserted into OPEN in ascending order of their cost: $f(n_1)= 001 (1)$ whereas $f(n_2) = 110 (6)$, so that $n_1$ goes first and $n_2$ is inserted second. $n_1$ is inserted into CLOSED.
  2. $n_1$ is expanded and $n_3$ is generated with a cost equal to $f (n_3) = 001 | 010 = 011 (3)$. Still, $n_2$ is second as $n_3$ is inserted before it. $n_1$ is inserted into CLOSED.
  3. $n_3$ is expanded and the goal $t$ is generated with a cost equal to $f (t) = 011 | 100 = 111 (7)$. Hence, the goal is inserted into OPEN after $n_2$. $n_3$ is inserted into CLOSED
  4. Now, $n_2$ is expanded and $n_3$ is generated with a cost equal to $f (n_3) = 110 | 010 = 110 (6)$ which is lower than the cost of the next node in OPEN (the goal, with a cost equal to 7). Hence, $n_3$ is re-inserted into OPEN with a cost equal to 6.
  5. Phew! You might be thinking that $n_2$ gets a chance to discover a cheapest path to the goal. Unfortunately not!! Point is that $n_3$ is found in CLOSED and hence, it is immediately discarded!
  6. The next node in OPEN is the goal with a cost equal to 7.

Dijkstra halts with the solution $\langle s, n_1, n_3, t\rangle$ which is incorrect as it has a cost equal to 7 units, whereas the path $\langle s, n_2, n_3, t\rangle$ has a lower cost, 6 units.

In the Figure above, thick vertices ($n_1$, $n_3$ and $t$) represent the problematic vertices: it can be easily verified that the bitwise OR of the involved costs equals 111 and, moreover, they are laid out in increasing order of cost so that there is no way for Dijkstra to foresee the trap until it is too late.

Fixing the problem does not seem easy. A simple way consists of getting rid of CLOSED and let Dijkstra just enumerate all paths in increasing order of their $f$-value. Note however that the number of paths can grow exponentially and hence this might be impractical. It is my feeling that there should be better ways than just running this modified version of Dijkstra.

Hope this helps,

$\endgroup$
  • $\begingroup$ Oh, you are right! I went too fast. The difference been that the cost is computed as the bitwise or of the edge costs of the sequence traversed, right? (as opposed to the bitwise or of the nodes). Still the same argument applies though I should edit my answer. $\endgroup$ – Carlos Linares López Jun 22 '16 at 8:36
  • $\begingroup$ D.W., I edited the answer and any comments would be very welcome. $\endgroup$ – Carlos Linares López Jun 22 '16 at 9:09
  • $\begingroup$ 1. "the cost of each edge is state-dependent" - I don't think that's right. The cost of edge $(n_1,n_2)$ is just $c(n_1,n_2)$. Similar comments apply to the rest of that paragraph. (Perhaps this might be a matter of terminology?) 2. " I will then show it is strictly equivalent to your case." - I don't see why this should be true. There might be a similar counterexample for both problems that shows Dijkstra's algorithm doesn't work for either of them, but that doesn't mean they are equivalent. $\endgroup$ – D.W. Jun 22 '16 at 16:45
  • $\begingroup$ 3. Good counterexample! That's very convincing. I think you can just present that counterexample and remove all mention of the other case (where $c(n_1,n_2)=n_1|n_2$). $\endgroup$ – D.W. Jun 22 '16 at 16:46
  • $\begingroup$ I know that state-dependent was rather ambiguous so that is why I tried to explain it a little bit deeper. The counterexample shown shows that in any graph where edges are labeled with bits has an associate graph where costs are attached to nodes instead of edges. Anyway, I think you are right and it is better to go straight to the point so that I do promise to edit my solution. Anyway, I really liked the answer from Mihai as well! $\endgroup$ – Carlos Linares López Jun 22 '16 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.