Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Number of shortest path

52 views
Skip to first unread message

dvdsum

unread,
Jun 13, 2006, 3:31:00 PM6/13/06
to
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...

Thank you!!!

0 new messages