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

i'm in need of piece of code finds shortest path between nodes greatest weighting. example, quickest route d, greatest weighting:

  - b- --e      /  \ /        d      \  / \       c - -f 

so right shortest abd or acd. once weighting applied, code should choose longest path out of 2 (counter-intuitive, huh?).

i'm trying modify algorithm dijkstra's algorithm, end traversing entire graph. know how this? algorithm can code myself immensely.

1. run bfs source (let s) on graph find length of shortest path s target t, let d. mark d(s,v) - distance s node v.
2. create subgraph g'=(v',e') of g such that: v in v' if distance source (s) @ d - d(s,v) <= d. e=(u,v) in e' if: both u , v in v'.
3. create new graph g*=(v*,e*), v'=v*, , edge (u,v) in e* if in e' , d(s,u) < d(s,v).
4. set new weight function w*(u,v) = -w(u,v), , run bellman ford on g* using w*.
5. the heaviest shortest path in g s t of weight -d(t), , path found bf matching one.

time complexity of algorithm o(ve), since bellman-ford bottleneck.

---

correctness proof

claim 1: shortest path s t not contain cycles.
proof simple removing cycle shorter path.

claim 2: shortest paths s t in g'
proof: since shortest paths s t of length d, , eliminated nodes distance s longer d, remove nodes not needed shortest paths.

claim 3: shortest paths s t in g*.
proof: assume removed edge (u,v) in shortest path, , let path s->...->x->u->v->y->...->t. note path v->y->..->t of length d-d(s,u)-1 (assuming d(s,u) minimal)
however, note construction of e*, d(s,v) <= d(s,u) (otherwise (u,v) wouldn't have been removed). so, there path s->...->v->y->...->t distance s: d(s,v) + d-d(s,u)-1 <= d(s,u) + d - d(s,u) -1 <= d-1 - contradiction minimality of d.

claim 4: there no cycles in g*.
proof: assume there cycle in g*: v1->v2->vk->v1. definition of g', nodes reachable s. without loss of generality, let assume d(s,v1) minimal other d(s,vi) (otherwise rotate indices match assumption). there path v1->v2->...->vk->v1, , d(s,v1)=d(s,v1). means @ least 1 edge (vi,vi+1) in path, d(vi) >= d(vi+1) - contradicting construction of e*, , cycle not exist in g*.

claim 5: algorithm correct.

from correctness of bellman-ford, , since g* not contain negative cycles (no cycles @ all), bf find path minimal weight according w* in g*. path 1 maximal weight according w, construction of w*.
since shortest paths in g exist in g* (and them), path shortest path in g maximal weight.

qed