dvdsum wrote: > Hello! can you help me please??! > > We are given a directed graph G = (V,E), with costs on the edges; the > costs may be positive or negative, but every cycle in the graph has > strictly positive cost. We are also given two nodes v, w. Give an > efficient algorithm that computes the number of shortest v-w paths in > G. The algorithm should not list all the paths; hist the number > suffices. > > > Please help meeee! > > > I think I must use Bellman-Ford, but I don't know...
First, I'll assume you're talking about any v-w paths, not necessarily simple. Otherwise the problem is NP-hard. Here's a easier version of the problem: determine the number of simple v-w paths, i.e., ignore weights. Next, use Bellman-Ford to reduce your problem to the easier version. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
