×

# finding shortest path in a graph with good and bad edges

 0 1 Hi everyone! I've been stuck on this problem for a while: http://wcipeg.com/problem/ccc11s2p2 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 157●1●8 accept rate: 10% One thing. m<= 10^4, not 10^5 ;) (31 Aug '15, 00:25) nibnalin6★

 1 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 150●3 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) 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)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×2,698
×1,197
×164
×125

question asked: 30 Aug '15, 22:30

question was seen: 2,632 times

last updated: 03 Sep '15, 14:23