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

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

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
    
That's not an excuse for giving an SE-bad answer. If you feel that way, please don't answer (or wait a week or two) or put your hint in a comment. Cf our homework policy (as per this). –  Raphael Jan 28 '13 at 22:15

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.