You are not logged in. Please login at to post your questions!


finding shortest path in a graph with good and bad edges


Hi everyone!

I've been stuck on this problem for a while:

Basically, you're given a weighted undirected graph with n vertices and m edges (n<=1600, m<=10^5) where some of the edges are good and others bad. You have to find the shortest path between two vertices among all such paths whose sum of weights of bad edges is at most a given threshold S (S<=3600).

I tried modifying Dijsktra's algorithm (add a vertex to the visited set only if the sum of bad edges on the path from the source to that vertex is at most S)- but it's not too hard to find testcases for which this fails.

Any help will be appreciated. Thanks :)

asked 30 Aug '15, 22:30

AnonymousBunny's gravatar image

accept rate: 10%

One thing. m<= 10^4, not 10^5 ;)

(31 Aug '15, 00:25) nibnalin6★

I would suggest a DP for that matter: DP[node][bad_sum] -> the minimum path to the "node" vertex using bad edges of sum bad_sum <= S. You can then implement a Dijkstra (or Bellman-Ford) algo to fill the matrix, i.e.:

You keep a min heap that keeps two parametres (the vertex "node" and the bad sum "bad_sum", and at each time pop the min and push the adjacent cells (if you augment the DP matrix). This Works only if edges have positive costs. If they can have negative cost, then you're stuck with Bellman-Ford. Good luck!


answered 30 Aug '15, 23:55

retrograd's gravatar image

accept rate: 12%

(sorry for the late reply) Yes, the edges are positive :) I don't entirely understand the "augmenting the matrix" part, but I think I get the basic idea. Thanks! :)

(02 Sep '15, 12:36) AnonymousBunny5★

By "augmenting the matrix" I was just saying that we "make it a little better" by changing its value into a smaller one :).

(03 Sep '15, 14:23) retrograd6★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 30 Aug '15, 22:30

question was seen: 2,632 times

last updated: 03 Sep '15, 14:23