# Modified shortest path problem

For a given graph $$G=(V,E)$$ and a given weight function $$W$$ lets say we define the new weight for path p to be the regular weight minus the heaviest edge in that path, i.e: $$w^*(p)=\varSigma(w(v_i,v_{i+1}) -max\{w(v_i,v_{i+1})) | 1\leq i \leq k$$}

The complexity needs to be $$O(V+E\log V)$$. Obviously i thought about dijkstra, define a new weight function s.t shortest path according to that weight function is the shortest path we looking for, and that just run dijkstra algorithm on the graph using the new weight function, however I cant think about such function, does anyone have an idea? Thanks in advance.

• Is the weight function $W$ non-negative? This is the only circumstance in which Dijkstra will work; otherwise you'll need to use Bellman-Ford's algorithm. Jun 1, 2020 at 15:51
• Yes, sorry I forgot to mention this Jun 1, 2020 at 18:42

Create 2 copies of $$G: G_1,G_2$$. For every edge $$e=(v,u)\in G$$ also add an edge $$(v_1,u_2)$$ between the node $$v$$ of $$G_1$$ and $$u$$ of $$G_2$$. Make those edge's weight to $$0$$.
Now, find a shortest path between $$s_1$$ and $$t_2$$ (using Djikstra)