# Pareto-optimal shortest paths

Given a directed graph on the nodes 0, 1, ..n, where each edge has two non-negative integer costs, return the set of all possible Pareto Optimal path costs between node 0 and node n.

These are the costs of paths for which you cannot decrease the first component of the cost without increasing the second component, and conversely.

In the examples, I have given the input as a dictionary of edge costs, but you could also take a matrix of edge costs, or a list of edges with their corresponding costs.

Examples:

{(0, 1): (1, 4), (1, 2): (4, 2), (0, 2): (2, 1)} -> [(2, 1)]

{(0, 1): (2, 2), (2, 3): (4, 2), (0, 2): (3, 1),
(0, 3): (1, 4)} -> [(1, 4), (7, 3)]

{(1, 4): (2, 4), (2, 3): (2, 1), (1, 2): (3, 1),
(3, 4): (4, 1), (0, 1): (2, 2), (2, 4): (1, 4),
(0, 2): (1, 3)} -> [(4, 6), (2, 7), (7, 5)]

{(0, 3): (2, 4), (3, 5): (2, 4), (0, 1): (1, 1),
(1, 4): (4, 1), (1, 2): (2, 1), (3, 4): (1, 1),
(1, 3): (2, 2), (4, 5): (4, 2)} -> [(4, 8), (9, 4), (5, 7), (8, 6)]

{(1, 2): (2, 1)} -> []



Reference solution in Python using breadth-first search:

def shortest_paths(graph):
N = max(i for t in graph for i in t) + 1

adj = [[] for _ in range(N)]
for (i, j) in graph:

costs = [[] for _ in range(N)]
costs[0].append((0, 0))

queue0 = [((0, 0), 0)]
queue1 = []
while queue0:
for ((c0, c1), i) in queue0:

(d0, d1) = graph[(i, j)]
e0, e1 = c0 + d0, c1 + d1

#dominated by or equal to an existing path
if any((f0 <= e0) and (f1 <= e1) for f0, f1 in costs[j]):
continue

#keep only non-dominated paths
costs[j] = [(f0, f1) for (f0, f1) in costs[j] if (f0 < e0) or (f1 < e1)]
costs[j].append((e0, e1))

queue1.append(((e0, e1), j))

queue0, queue1 = queue1, queue0
del queue1[:]
return costs[-1]

• This seems a good question, but it's a bit hard to understand. Maybe a worked out example would help? Feb 27 at 13:12
• You should add the following example to ensure distinct results: {(0, 1): (0, 0), (1, 2): (0, 0), (0, 2): (0, 0)} -> [(0, 0)] Mar 2 at 13:31
• Do all edges increase current node id?
– l4m2
Mar 7 at 7:22
• @l4m2 No, (i, j) and (j, i) can have different costs. Mar 7 at 13:41
• Then you should add such example
– l4m2
Mar 8 at 0:29

# Kotlin, 248228 211 bytes

fun Set<IntArray>.p(i:Int=0):Set<Pair<Int,Int>>
=if(i==maxOf{it[1]})setOf(0 to 0)else
filter{it[0]==i}.flatMap{p(it[1]).map{(a,b)->a+it[2]to b+it[3]}}.run{filter{(a,b)->all{(c,d)->a<c||b<d||a==c&&b==d}}}.toSet()


try on playground

# Scala 3, 234 bytes

A port of @Cactusroot's Kotlin answer in Scala.

Golfed version. Attempt This Online!

def p(s:Set[Array[Int]],i:Int=0):Set[(Int,Int)]={if(i==s.map(_(1)).max)Set((0,0))else s.filter(_(0)==i).flatMap(a=>p(s,a(1)).map{case(x,y)=>(x+a(2),y+a(3))}).filter{case(x,y)=>s.forall{b=>val(c,d)=(b(2),b(3));x<c||y<d||(x==c&&y==d)}}}


Ungolfed version. Attempt This Online!

def p(set: Set[Array[Int]], i: Int = 0): Set[(Int, Int)] = {
if (i == set.map(_(1)).max) Set((0, 0))
else
set
.filter(_(0) == i)
.flatMap(arr =>
p(set, arr(1)).map { case (a, b) => (a + arr(2), b + arr(3)) }
)
.filter { case (a, b) =>
set.forall { arr =>
val (c, d) = (arr(2), arr(3))
a < c || b < d || (a == c && b == d)
}
}
}