wu :: forums « wu :: forums - no of shortest paths » Welcome, Guest. Please Login or Register. Nov 28th, 2024, 2:52am

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    cs (Moderators: Eigenray, Grimbal, SMQ, towr, Icarus, ThudnBlunder, william wu)    no of shortest paths « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: no of shortest paths  (Read 506 times) algo_wrencher Newbie I am not insane, I enjoy every moment of it!     Posts: 44 no of shortest paths   « on: Jan 30th, 2007, 9:06pm » Quote Modify is it possible to find the number of shortest paths in a graph in time O(V+E)? IP Logged towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: no of shortest paths   « Reply #1 on: Jan 31st, 2007, 1:27am » Quote Modify Wouldn't that be either V or E (depending whether you consider zerolength paths)? IP Logged Wikipedia, Google, Mathworld, Integer sequence DB sachinutd Newbie     Posts: 4 Re: no of shortest paths   « Reply #2 on: Jan 31st, 2007, 4:03am » Quote Modify algo_wrencher Did you mean shortest paths between every pair of nodes or just between two nodes? IP Logged Grimbal wu::riddles Moderator Uberpuzzler     Gender: Posts: 7527 Re: no of shortest paths   « Reply #3 on: Jan 31st, 2007, 4:49am » Quote Modify 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. IP Logged algo_wrencher Newbie I am not insane, I enjoy every moment of it!     Posts: 44 Re: no of shortest paths   « Reply #4 on: Jan 31st, 2007, 8:08am » Quote Modify Sorry, you are also given 2 nodes s & t on the graph. Thanks. IP Logged Pages: 1  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board