# Calculating multi-objective shortest path for a graph in Mathematica

I would like to calculate multi-objective shortest path for a graph which edges have multiple weights (distance, delay, cost, for example) using e.g. Martins' algorithm. Is it possible doing that using built-in functions of Mathematica? If not, what could I do?

• No, this algorithm is not built in. You have to implement it from scratch. – Szabolcs Nov 30 '16 at 8:57
• Got it, thanks. Any advise how could I assign an array of weights like [3, 5, 7] to an edge? – Vladimir Dec 1 '16 at 20:30

In this context "shortest" has meaning only for an effective scalar value at each weight. So if you have several edge properties (distance, delay, cost, etc.), then you must first create a function that reduces the set of edge properties into a single scalar "weight" for each edge. It could be, for instance, $w = dis + 2 delay + 5 cost$. (Weights should be non-negative, in general.)

Once you have such a scalar for each weight, grouped into a list, use, for example:

mygraph = PetersenGraph[4, 1,
EdgeWeight -> {3,2,8,5,6,2,9,4,1,8,12,1}]


and then

FindShortestPath[mygraph, 1, All]

• David, obviously, your proposal (using so-called Composite Objective) is not equal to multi-objective optimization in general. That is why, Martins has proposed his algorithm of multi-criteria shortest path, which finds an optimal path by processing multiple objectives simultaneously. – Vladimir Dec 1 '16 at 20:27