Modifying Dijkstra's Algorithm to find shortest path with largest weighting

Question

I'm in need of a piece of code that finds the shortest path between nodes with the greatest weighting. For example, the quickest route from A to D, but with the greatest weighting:

  - B- --E
     /  \ /
    A    D
     \  / \
      C - -F

So right now the shortest would be ABD or ACD. Once the weighting is applied, the code should choose the longest path out of the two (counter-intuitive, huh?).

I'm trying to modify an algorithm for Dijkstra's Algorithm, but ultimately I just end up traversing the entire graph. Would anyone know how to do this? Even just an algorithm so I can code it myself would help immensely.

Answer 1

You can use Dijkstra if you adjust your weights.

If your optimal path must be one that visits the fewest nodes, you can use a high penalty p for traversing each edge and subtract the real weight:

    w' = p − w

The penalty must be chosen higher than the highest weight w_max to prevent negative values for w', for which Dijsktra doesn't work. It must also be high enough so that really the shortest path is chosen. A good estimate for p for a graph of n nodes might be:

    p ≈ n·w_max

(Edit: My original answer proposed to use reciprocal weights w' = 1/w of each edge instead of the real weight w as an alternative. This will not necessarily give you the shortest path, but one whose weight is high while traversing few edges. This solution does not work for many cases. It is, however, totally independent from the penalty method, which doesn't use reciprocal values.)

Answer 2

1. Run BFS from the source (let it be s) on the graph to find the length of the shortest path from s to the target t, let it be d. Also mark d(s,v) - the distance from s to any node v.
2. Create a subgraph G'=(V',E') of G such that: v is in V' only if its distance from the source (s) is at most d - d(s,v) <= d. e=(u,v) is in E' only if: both u and v are in V'.
3. Create a new graph G*=(V*,E*), where V'=V*, and an edge (u,v) is in E* if it is in E' AND d(s,u) < d(s,v).
4. Set a new weight function w*(u,v) = -w(u,v), and run Bellman Ford on G* using w*.
5. The heaviest shortest path in G from s to t is of weight -d(t), and the path found by BF is the matching one.

Time complexity of the algorithm is O(VE), since Bellman-Ford is the bottleneck.

---

Correctness Proof

Claim 1: The shortest path from s to t does not contain any cycles.
Proof is simple by removing the cycle we get a shorter path.

Claim 2: All shortest paths from s to t are in G'
Proof: Since all shortest paths from s to t are of length d, and we eliminated only nodes with distance from s longer than d, we remove only nodes not needed for shortest paths.

Claim 3: All shortest paths from s to t are in G*.
Proof: Assume we removed some edge (u,v) in a shortest path, and let that path be s->...->x->u->v->y->...->t. Note that the path v->y->..->t is of length d-d(s,u)-1 (assuming d(s,u) is minimal)
However, note that from construction of E*, d(s,v) <= d(s,u) (otherwise (u,v) wouldn't have been removed). So, there is a path s->...->v->y->...->t with distance from s: d(s,v) + d-d(s,u)-1 <= d(s,u) + d - d(s,u) -1 <= d-1 - contradiction to minimality of d.

Claim 4: There are no cycles in G*.
Proof: Assume there is a cycle in G*: v1->v2->vk->v1. By definition of G', all nodes are reachable from s. Without loss of generality, let us assume d(s,v1) is minimal for all other d(s,vi) (otherwise rotate indices to match this assumption). But there is a path v1->v2->...->vk->v1, and d(s,v1)=d(s,v1). This means at least for one edge (vi,vi+1) in this path, d(vi) >= d(vi+1) - which is contradicting the construction of E*, and the cycle does not exist in G*.

Claim 5: The algorithm is correct.

From correctness of Bellman-Ford, and since G* does not contain negative cycles (no cycles at all), BF will find the path with minimal weight according to w* in G*. This path is the one with maximal weight according to w, from the construction of w*.
since all shortest paths in G also exist in G* (and only them), this path is also the shortest path in G with maximal weight.

QED