# BFS in K shortest paths

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?

• 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

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).

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

• 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 'SO- stop being evil' 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. – A.B. Jan 29 '13 at 1:25

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

• 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