On Jun 27, 10:54 am, venkat kumar <[email protected]> wrote: > in single source shortest path ,having neg cost edges is good but: > > 1)it may > lead us goto into a loop of arbitrary time > in the meanwhile we can have another path with minimum positive cost but > with less time. > now by taking time factor into consideration,ie,larger path with neg cost or > smaller path with larger cost > how to code this??
I'm not sure what you mean. The Floyd-Warshall algorithm will solve the all-pairs SP problem correctly even if there are negative edge weights. If there is a negative cycle that includes node N, then it will show a negative value for the SP from N to N. This is the total negative value for one trip around the cycle. Of course you can keep getting paths of less weight for all nodes on any negative cycle by traversing the cycle as many times as you like. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
