1
$\begingroup$

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?

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

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]
|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Vladimir Dec 1 '16 at 20:27

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.