Power set ordered by sum and Dijkstra shortest path

Question

I've needed to enumerate the power set ordered by the sum of elements in each subset. Luckily I've found a nice solution here: Algorithm wanted: Enumerate all subsets of a set in order of increasing sums.

But I'm still wondering if this is an equivalent of Dijkstra shortest path algorithm.

Empty set is the source, target is the whole set, and each subset's distance from the source is the sum of the elements in them.

The graph which is enumerated is the lattice of subsets or $(2^N,\cup, \cap)$, where $N$ is the whole set.

For example, let $N=\{1,4,5,9\}$, then:

$d(\emptyset,\{1\})=1$ and $d(\emptyset,\{1,4\})=5$, as defined above and therfore $d(\{1\},\{1,4\})=d(\emptyset,\{1,4\})-d(\emptyset,\{1\})=4$.

Answer 1

No, the algorithm described in the other post is not quite the same as Dijkstra's algorithm executed on the lattice. It uses an additional property of the lattice to "prune" the search that Dijkstra's algorithm does at each iteration. The goal is to tweak Dijkstra's to make it more efficient. (But as I note below it is not clear that it achieves this goal.)

To explain, I'll describe what Dijkstra's algorithm on the lattice would do, and then describe how the other algorithm can be viewed as a modification of that.

Dijkstra's algorithm maintains the collection $K$ of all subsets of $N$ enumerated ("known") so far. At each iteration it does the following. It adds to $K$ the cheapest subset, say, $S'$, not yet in $K$. To do this efficiently, Dijkstra's algorithm maintains, for each set $S\not\in K$, a value $D[S]$ which is the cheapest way to make $S$ by adding just one element to some set already in $K$. It finds $S'$ by choosing the subset $S$ with minimum $D[S]$.

Dijkstra's stores the values $D[S]$ for $S\not\in K$ in a min-heap so that the desired minimum can be found quickly (in time logarithmic in the number of values). However, note that this number of values can be exponential, because there is one for every subset not yet in $K$. (As an aside, because heap operations take time logarithmic in the number of keys stored, I think Dijkstra's on the lattice does actually have polynomial delay for this problem.)

The linked-to algorithm uses the following observation. For each element $i\in N$, it maintains the cheapest set $S_i$ in $K$ that does not contain $i$. Then, it only needs to consider, in each iteration, the sets of the form $S_i\cup\{i\}$ for each $i$. This is polynomially many, instead of exponential, and one of the sets of this form will be the set that Dijkstra's would choose (the next cheapest set).

On the other hand, Step 4 of that algorithm, which updates $S_i$ when $S_i\cup\{i\}$ is added to $K$, is not clearly polynomial, because it has to scan through $K$ to find the next value for $S_i$. So, because of its Step 4, unlike Dijkstra's algorithm, that algorithm does not clearly have polynomial delay between enumerated sets.

EDIT 1: It seems this would be easy to fix by maintaining for each $i$ the subset $K_i$ of $K$ of sets that don't contain $i$ (ordered by cost). When a set $S$ is added to $K$, it would be appended to each $K_i$ such that $i\not \in S$. Then the update to $S_i$ would take constant time, so the whole algorithm would have polynomial delay between sets.

EDIT 2: By the way, a poly-delay algorithm for a more general problem is described in an answer to this related question: https://cstheory.stackexchange.com/questions/47023/can-we-efficiently-enumerate-the-words-accepted-by-a-dfa-by-order-of-increasing

Answer 2

Well these two are not same. Consider the first step in Dijkstra. In Dijkstra, we start with the source, iterate over all the edges starting from source and select the edge with the lowest weight among them . So even though there exists a edge with a lesser wight between two vertices where none of them are the source, Dijkstra will not select that first.

Also, there are $2^{|E|}$ subsets of edges for a graph with |E|-edge and Dijkstra algorithm does not enumerate all of them, being a polynomial time algorithm.

Also it reduces the distance between two vertices after "fixing" any vertex, if possible. That means, it does not always, produce a subset of edge (present in the path) in the order or increasing sum.

So they have lots of differences.