Tell me more ×
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.
up vote -1 down vote favorite
1

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 at 23:33

3 Answers

up vote 0 down vote

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 at 10:06
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 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 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 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 at 1:24
show 4 more comments
up vote 0 down vote

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 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. – moller1111 Jan 29 at 1:25
up vote 0 down vote

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.