Shortest Path Maximum Profit

An answer to this question on Stack Overflow.

Question

Suppose you have an undirected Graph G=(V,E) and two vertices s,t in V, s not equal t. Every Edge e in E has a length and a profit.

The problem is: How can I find a path P=(s,a1,a2,...,t) between s-t such that the total length of the path is the minimum possible and the profit is the maximum possible. With Dijkstra I can find the first constraint, but How can I be sure for the second one?

You can do a backtrack but, Is there any faster algorithm? Any help is welcome.

EDIT: First find the value x of the shortest path, then over the set of all the paths with the same length x, find one with the maximum profit.

See this picture: enter image description here

Answer

This seems like an example of multi-objective optimization.

One way to approach such a problem is to make a new variable, L for lambda.

But first, let's deal with the profit issue: Your edges have lengths l and profits p. Redefine all of the p such that p'=max(p)-p. Now, your maximally profitable edge has a value of zero (lowest possible) and your least-profitable edge has a value of max(p) (highest possible). You can now find the least cost-path.

Define the weight of an edge as being l*L+p'*(1-L), now vary L from 0 to 1. Different paths will be optimal depending on whether the length or profit is more important. Loosely speaking, these paths form a Pareto optimal set. Each solution path is better than all others for that particular value of L. For that L there is no way to increase profit without also increasing length, or to decrease length without decreasing profit.

Note that choosing appropriate values of L to generate this set may not be straight-forward: for instance, if profit numbers are much larger than length numbers, most of the set will cluster in values of L which scale the profit values to a level where they are comparable with the length values. These L values may be quite small.

Ooop, saw your edit: "First find the value x of the shortest path, then over the set of all the paths with the same length x, find one with the maximum profit." In this case, Nick's answer is the way to go.