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.

  • $\begingroup$ 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. $\endgroup$ – Or Bairey-Sehayek Jun 1 at 15:51
  • $\begingroup$ Yes, sorry I forgot to mention this $\endgroup$ – user2207686 Jun 1 at 18:42

Notice that if you allow once jumping without paying the weight cost, then the shortest path is exactly what you need.

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)

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.