graph breadth first search
in [Lisp]
|
From: Antony on 24 Jun 2010 14:22 I was trying to code the BFS algorithm from the book algorithms - Cormen, Rivest 2nd ed pp 532 My question is would it work for weighted graphs simply by changing the logic where it says d[v] <- d[u] + 1 to d[v] <- d[u] + edgeweight(u,v) -Antony
From: Tassilo Horn on 24 Jun 2010 14:38 Antony <spam+lisp_dot_linux(a)gmail.com> writes: Hi Antony, > I was trying to code the BFS algorithm from the book > algorithms - Cormen, Rivest 2nd ed pp 532 I don't have it, so my answer might be a bit vague. > My question is would it work for weighted graphs > simply by changing the logic where it says > d[v] <- d[u] + 1 > to > d[v] <- d[u] + edgeweight(u,v) d[v] is the distance of node v from the start vertex of the search, right? And your question is the algorithm will still find the shortest path from the start node to some target node, right? Then the answer is No. Or at least, you cannot break out of the loop as soon as you visit the target node the first time, but only as soon as all other distances are equal or longer than the currently shortest path. The reason is, that there may be a shorter (cheaper) path which still has more hops (edges). For that kind of tasks, have a look at the Dijkstra or A* algorithms. The former calculates the shortest path to *all* reachable nodes, while the latter finds the shortest path to some target node with minimal effort (and extends the Dijkstra algorithm with a heuristic). Bye, Tassilo
From: Antony on 25 Jun 2010 13:40 On 6/24/2010 11:38 AM, Tassilo Horn wrote: > Antony<spam+lisp_dot_linux(a)gmail.com> writes: >> My question is would it work for weighted graphs >> simply by changing the logic where it says >> d[v]<- d[u] + 1 >> to >> d[v]<- d[u] + edgeweight(u,v) > > d[v] is the distance of node v from the start vertex of the search, > right? And your question is the algorithm will still find the shortest > path from the start node to some target node, right? > > Then the answer is No. Or at least, you cannot break out of the loop as .... Thanks. I guessed as much after some more thought. Basically BFS finds the closest in terms of hops but not distances. > For that kind of tasks, have a look at the Dijkstra or A* algorithms. I will get to this sometime. -Antony
From: Tassilo Horn on 28 Jun 2010 06:23 Antony <spam+lisp_dot_linux(a)gmail.com> writes: Hi Antony, >>> My question is would it work for weighted graphs >>> simply by changing the logic where it says >>> d[v]<- d[u] + 1 >>> to >>> d[v]<- d[u] + edgeweight(u,v) >> >> d[v] is the distance of node v from the start vertex of the search, >> right? And your question is the algorithm will still find the >> shortest path from the start node to some target node, right? >> >> Then the answer is No. Or at least, you cannot break out of the loop >> as > ... > Thanks. I guessed as much after some more thought. Basically BFS finds the > closest in terms of hops but not distances. Yes, exactly. >> For that kind of tasks, have a look at the Dijkstra or A* algorithms. > I will get to this sometime. Ok, have fun. Bye, Tassilo
From: Tassilo Horn on 28 Jun 2010 06:28 Antony <spam+lisp_dot_linux(a)gmail.com> writes: Hi Antony, >>> My question is would it work for weighted graphs >>> simply by changing the logic where it says >>> d[v]<- d[u] + 1 >>> to >>> d[v]<- d[u] + edgeweight(u,v) >> >> d[v] is the distance of node v from the start vertex of the search, >> right? And your question is the algorithm will still find the >> shortest path from the start node to some target node, right? >> >> Then the answer is No. Or at least, you cannot break out of the loop >> as > ... > Thanks. I guessed as much after some more thought. Basically BFS finds the > closest in terms of hops but not distances. Yes, exactly. >> For that kind of tasks, have a look at the Dijkstra or A* algorithms. > I will get to this sometime. Ok, have fun. Bye, Tassilo
|
Pages: 1 Prev: importing symbols locally Next: Clisp backwards-combatibility - how to work around |