# shortest path optimization for multiple edge attributes

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?

## 1 Answer

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.

• it doesn't matter that they are different units? yrs and meters – jchaykow Oct 31 '18 at 6:05
• 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). – user20160 Oct 31 '18 at 6:11