2
$\begingroup$

Suppose I have a graph $G=(V,E)$, where each edge $e$ has both a non-negative length $\ell(e)$ and a non-negative cost $c(e)$. Given a start node $s$ and a destination node $t$, I want to find a set of Pareto-optimal paths $s \leadsto t$. In other words, for each budget $b$ in some set (say $\{0,1,2,\dots,B\}$), I want to find the shortest path $s \leadsto t$ whose cost is at most $b$. The length of a path is the sum of the lengths of its edges, and the cost of a path is the sum of the costs of its edges.

Is there an efficient algorithm to solve this problem?

$\endgroup$
2
2
$\begingroup$

I will outline two solutions. Both have the same asymptotic worst-case running time, namely $O(B \cdot |E| \cdot \log (B\cdot |V|))$, but the second might be slightly more efficient in practice.

Increase the size of the graph

Create a new graph $G'$ where edges have only lengths, not costs. Each vertex is of the form $\langle v,b \rangle$ where $v \in V$ is a vertex in the original graph and $b$ is a cost (the "cost so far"). For each edge $(u,v) \in E$ in the original graph and each $b$, add an edge $\langle u,b \rangle \to \langle v,b+c(u,v) \rangle$ whose length is given by $\ell(u,v)$.

Now, for each $b$, find the shortest path from $\langle s,0 \rangle$ to $\langle t,b \rangle$. This can be done all at once by using Dijkstra's algorithm in $G'$, starting at $\langle s,0 \rangle$; it will compute the distance to every vertex of $G'$ in time linear in the size of $G'$, and thus will compute the length of the shortest path to $\langle t,b \rangle$ for each $b$. The distance to $\langle t,b \rangle$ is then the length of the shortest path $s \leadsto t$ in $G$ that uses budget $b$.

Modify Dijkstra's algorithm

Normally, Dijkstra's algorithm maintains a distance $d[v]$ to each vertex $v$, which records the length of the shortest path $s \leadsto v$. We will maintain a "distance map" $d[v]$, which maps a budget $b$ to the length of the shortest path $s \leadsto v$ that uses budget $\le b$. We'll ensure that the "distance map" keeps only the Pareto-optimal entries in the map (e.g., if you have two entries $b_1 \mapsto \ell_1$ and $b_2 \mapsto \ell_2$ in the distance map where $b_1 \le b_2$ and $\ell_1 \le \ell_2$, then we delete the second entry). Also, we'll delete any entries in the distance map where the budget $b$ is greater than $B$.

Now, run Dijkstra's algorithm on $G$. Dijkstra's algorithm performs operations on distances, and we will convert them to operations on distance maps:

  • Where standard presentations of Dijkstra's algorithm write $d[u] + \ell(u,v)$, we will instead create a new distance map. For each entry $b \mapsto \ell$ in $d[u]$, the new distance map has an entry $b + c(u,v) \mapsto \ell + \ell(u,v)$.

  • Where standard presentations of Dijkstra's algorithm write "if $d' \le d[v]$, set $d[v] := d'$", we will instead merge the two distance maps, as $d[v] := \min(d[v], d')$. In particular, we just add all the entries of $d'$ to $d[v]$, and then reduce $d[v]$ to be Pareto-optimal.

Hopefully with these two ideas, it will be clear how to create the modified Dijkstra's algorithm. You might notice that this is doing more or less the same thing as the first algorithm, but now bundling a whole bunch of vertices of $G'$ together into a single distance map.

The primary benefit of the second algorithm is that reducing each distance map to only include Pareto-optimal entries at each point might decrease the amount of computation you need to do, since we prune paths that we already know are worse than some other path we've previously explored.

What data structure can you use to represent distance maps, so that all operations are efficient? One plausible choice is a balanced binary search tree, keyed on $b$. Then all operations mentioned above can be performed efficiently.

$\endgroup$
1
  • $\begingroup$ @PålGD, good point. Fixed, thank you! $\endgroup$
    – D.W.
    Dec 30 '21 at 23:50

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.