2
$\begingroup$

Say I have a network. The edges each have two attributes: age and height. How might I run a shortest path algorithm that optimizes on both age and height? And could I weight it so that it optimizes 0.7 on age and 0.3 on height, or vice versa?

$\endgroup$
2
$\begingroup$

Let $A_{ij}$ and $H_{ij}$ denote the age and height attributes of an edge from node $i$ to node $j$. Suppose we want to weight age and height by some fractions $\alpha$ and $\beta$, respectively. Then, we can construct the combined edge lengths $D$, where the length of an edge from node $i$ to node $j$ is $D_{ij} = \alpha A_{ij} + \beta H_{ij}$. This means the length of any given path when measured using the combined edge lengths is $\alpha$ times the path length when measured using age, plus $\beta$ times the path length when measured using height.

Using the combined edge lengths $D$, the shortest path between any two nodes (and its length) can be computed as usual. For example, using Dijkstra's algorithm.

$\endgroup$
  • 1
    $\begingroup$ it doesn't matter that they are different units? yrs and meters $\endgroup$ – jchaykow Oct 31 '18 at 6:05
  • $\begingroup$ Yes, this will affect the solution. But, how to deal with it is problem dependent. For example, you'd have to choose $\alpha$ and $\beta$ appropriately, and/or normalize age/height so that they have common units (e.g. standard deviations) or are unit-less (e.g. fraction of the max). $\endgroup$ – user20160 Oct 31 '18 at 6:11

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.