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$
$\endgroup$
2
-
$\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
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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]
answered Nov 29, 2016 at 23:47
-
$\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