   Algorithms and Graph theory help
  Hi all!I have two big questions that I need to answer for a school assignment, and I need some help.The questions are:A)Which of the following (see below) algorithms work with multigraphs (that is, graphs with one or more edges between two vertices/nodes)?What changes can you make for the ones that don't work to make them work?B)Which of the following algorithms work with negative cost/weight edges?What changes can you make for the ones that don't work to make them work?Algorithms:Prim'sKruskal'sDijkstra'sDepth first searchBreadth first searchTopological sort(order)My answers are:A)They all work, but that for topological sort the graph must be acyclic.B)Prim and Kruskal work w/o modification. Dijkstra does not work, and if you make a change to it to make it work it will turn into Prim.Breadth first search only works on unweighted graphs, hence there's nothing you can do to it to make it work on weighted.Topological sort does not work since it only works on acyclic graphs, and with negative weights you risk ending up in an infinite loop.Depth first search works w/o modification.So, am I totally wrong on everything or am I in the ball-park?Any hints and/or help is greatly appreciated!Thanks,SL    
  Do you mean Prim and Kruskal minimum spanning tree algorithms? I think they would both "work" with multigraphs but if you have two edges between the same two nodes with the same weight the answer won't be unique, but I guess even on a regular graph there doesn't have to be a unique minimum spanning tree, now that I think about it.Not sure why you're saying a breadth first search only works on an unweighted graph. I mean you can always do a breadth first traversal, just ignore the weights, but maybe I'm misunderstanding the question.Which Dijkstra algorithm? Shortest path? Not seeing why it wouldn't work on a multigraph. I mean basically if you have a graph G1 with nodes A, B, and C and edges A->B, B->C, and A->C, if the weight of A->B plus the weight of B->C equals the weight of A->C then that graph is functionally equivalent to the multigraph G2 {A->C and A->C} where the edges are unweighted or have equal weight so any algorithm that fails on G2 would also have to fail on G1, but they don't, right?[Edited by - jwezorek on May 8, 2010 7:21:34 PM];  Hello!I´ll just borrow this thread for a sec if it´s cool.I am reeding some about graphs and was wondering how did you get Dijkstra's to prims when using negative weights. Do you have any site that i could check out with info about this ?;  Both Kruskal and Prim have running times that are greater than O(E) so without changing the time complexity for negative weights you can make two initial passes one in which you find the lowest negative weight L and another in which you add -L to the weights of all of the edges. However, I think at least in the case of Kruskal this isn't necessary.EDIT: Sorry misread the question but, I think, the same goes for Dijkstra (shortest path)[Edited by - jwezorek on May 18, 2010 7:31:56 AM];  jwezorek  I thought the same but apparently you cannot use negative weights for  Dijkstra. I haven't really looked in to it so deeply so my knowledge within that area isn't that good.I tried to find information about how you can modify the dijkstra algorithm so that you can use negative weights but i cant find any info about that so thats my main problem and it would be great if anyone could explain or post a page that covers it.   ;Quote:I tried to find information about how you can modify the dijkstra algorithm so that you can use negative weights but i cant find any info about that so thats my main problem and it would be great if anyone could explain or post a page that covers it.Well, isn't it O(E log V)? Can't you just re-weight the graph in O(E) as I said above.;  I have a solution for dijkstra with neg weights. Let me see if I can find it...   ;  Alright, let's see if I can get this right...The problem, first, with neg weights, is that once a vertex 'u' is declared 'known', it is possible that from some other, 'unknown' vertex 'v' there is a path back to u that is very negative.The offset-solution that jwezorek suggested might not work, here's why:Paths with many edges can become more weighty than paths with few edges.What you do is you use a combination of weighted and unweighted algorithms.This will however be costly big-oh wize...First, forget about the 'known'-concept, we need to be able to change our minds.Heres the pseudo-code:for each vertex v    v.dist=infinitys.dist = 0queue.enqueue(s)for as long as the queue is non-empty    vertex v = queue.dequeue()    for each vertex w adjacent to v   if( v.dist + cvw < w.dist )   w.dist = v.dist + cvw   w.path = v   if( w is not already in queue )   queue.enqueue(w)Running time is O(|E|*|V|)This is all from Data Structures and Algorithm Analysis in Java by Mark Allen Weiss from Pearson International Edition.   ;Quote:Original post by jwezorekWell, isn't it O(E log V)? Can't you just re-weight the graph in O(E) as I said above.You can get the wrong answer by re-weighting the graph. Here's some simple examples:You have a directed graph with three nodes. A, B and C. A->B cost is 1. A->C cost is -1. C->B cost is 1. That means the shortest path from A->B is clearly via C at a total cost of zero.If you add 1 to all those weights then going direct from A->B costs 2. So does going A->C->B. Dijkstra's algorithm now has a 50/50 chance of picking the A->B solution, which isn't shortest for the original unbiased graph.You can make the cheaper route worse after biasing by adding extra nodes. A->B=1, A->C=-1, C->D=-1, D->E=1, E->B=1. That gives again zero cost for the long route (A->C->D->E->B), and 1 for the short one. However after adding 1 to all weights the long route is cost 4, and the short is cost 2.Edit: I got a bit distracted while writing this, and StorLiten beat me to it...   ;  Oh, yeah...So with negative weights you have to use Bellman–Ford?   