Dijkstra with bitwise OR of edge costs

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?

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

StackExchange Computer Science Q#59790, answer score: 6