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?
-
$\begingroup$ No, this algorithm is not built in. You have to implement it from scratch. $\endgroup$– SzabolcsNov 30, 2016 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$– VladimirDec 1, 2016 at 20:30
1 Answer
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]
-
$\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$– VladimirDec 1, 2016 at 20:27