What about a simple greedy search? For every segment A -> B -> C in the shortest path, check if there is some A -> X -> C (or A -> X -> B -> C if you want to be thorough) that increases the value of the secondary weight. In each iteration, find every such variation, and then pick the one with the biggest 'secondary weight / primary weight' ratio. It iterates until the path either exceeds the X% constraint or until it reaches some arbitrary iteration limit. It would be O(n^3) I think, but if performance isn't a significant problem, it would find a reasonably good solution.