6
\$\begingroup\$

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:
        adj[i].append(j)

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

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

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

2 Answers 2

3
\$\begingroup\$

Kotlin, 248 228 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

\$\endgroup\$
1
\$\begingroup\$

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)
        }
      }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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