# 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. – Or Bairey-Sehayek Jun 1 at 15:51
• Yes, sorry I forgot to mention this – user2207686 Jun 1 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)