Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Do we need to use BFS or DFS algorithm to find the k shortest loopless paths in a graph between any two nodes? If so where can it be useful?

share|improve this question
    
What are your thoughts on the matter? A question as flat as this is unlikely to attract good answers. –  Raphael Jan 28 '13 at 23:33

3 Answers 3

Consider the case $k=1$ first. Can you use BFS or DFS? Now try to generalize.

share|improve this answer
1  
Can you elaborate a tad, maybe behind spoiler tags? As it stands, this answer is merely a comment. (A very helpful one, granted.) –  Raphael Jan 28 '13 at 10:06
1  
That's a homework exercise, I don't want to solve other people's homework for them. I already passed the class. –  Yuval Filmus Jan 28 '13 at 14:35
1  
If you're not happy with the answer, downvote it and/or write your own. Of late the site is full of homework questions by students too lazy to answer them on their own, trying their luck here, expecting us to do their work for them. Sometimes I feel like answering it anyway, sometimes not. This time I don't feel it. If that contradicts the homework policy, too bad. –  Yuval Filmus Jan 28 '13 at 22:47
1  
You are not wrong (and I, as a user, often feel the same way), but again, that's not a reason to give poor answers (speaking as a mod). I also feel that "too bad" is not the response an experienced, integral member of the community should have when addressed for acting against established policy; do we need to talk about this on meta? –  Raphael Jan 28 '13 at 23:30
1  
@Raphael the policy states that "this is my hw, what do i do" type of questions would be dealt with using quality control tools. i don't see this happening at all and the site is full of this kind of questions. –  Sasho Nikolov Jan 29 '13 at 1:24

For k=1.

I would like to draw your attention to the Theorem 22.5: Cormen
"upon termination d.v = ð(s,v) for all v € V"

ð(s,v) ... the minimum number of edges from s to v

share|improve this answer
    
This is more like a tip than an answer. Please don't ask readers to go and read a book to find the actual answer. You don't have to write a full formal proof for every question, but please at least summarize the main steps of reasoning, and leave the reference for those who want something fully written out. –  Gilles Jan 28 '13 at 23:43
    
@Gilles: since i quoted the Theorem, he doesn't need to click the link/read the book chapter. That was an indirect answer to his question that he should use BFS instead of DFS. You were right if i had said for example: "read the Chapter X of Cormen book", which i definitely didn't do. –  Hasan Tahsin Jan 29 '13 at 1:25

Whenever they ask for shortest paths in a graph, it is a safe bet that some form of BFS is called for (you need to first check the neighbors of the starting point, if none qualifies you need to check all their neighbors, and so on. I.e., BFS).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.