wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> no of shortest paths
        
(Message started by: algo_wrencher on Jan 30^th, 2007, 9:06pm)

Title: no of shortest paths
Post by algo_wrencher on Jan 30^th, 2007, 9:06pm

is it possible to find the number of shortest paths in a graph in time O(V+E)?

Title: Re: no of shortest paths
Post by towr on Jan 31^st, 2007, 1:27am

Wouldn't that be either V or E (depending whether you consider zerolength paths)?

Title: Re: no of shortest paths
Post by sachinutd on Jan 31^st, 2007, 4:03am

algo_wrencher
Did you mean shortest paths between every pair of nodes or just between two nodes?

Title: Re: no of shortest paths
Post by Grimbal on Jan 31^st, 2007, 4:49am

If you are looking for the nb of paths between 2 specified nodes and the path length is the number of edges, then it can be done easily.

Create arrays giving for each node
- dist: the distance from the start
- ways: the nb of ways to reach it.

- initialize dist to #edges+1, set dist[start]=0
- initialize ways to 0, set ways[start]=1.

- create toVisit: a list of edges to visit, add the starting node to it.
- for each node v in toVisit (in fifo order):
. - if v is the end, ways[v] is the answer.
. - for all items w that can be reached from v
. - else if dist[w]>dist[v]+1
. - set dist[w] = dist[v]
. - set ways[w] = ways[v]
. - add w to toVisit
. - else if dist[w]= dist[v]+1
. - add ways[w] += ways[v]

or something like that. It assumes the neighbours of a node can be found directly.

Title: Re: no of shortest paths
Post by algo_wrencher on Jan 31^st, 2007, 8:08am

Sorry, you are also given 2 nodes s & t on the graph. Thanks.