# finding longest path in an undirected and unweighted graph **URL:** \ **Category:** general\ **Tags:** diameter, graphs, breadth-first-search\ **Created:** [September 17, 2014, 6:37am UTC](https://discuss.codechef.com/t/finding-longest-path-in-an-undirected-and-unweighted-graph/7160 "2014-09-17T06:37:55Z")\ **Posts on this page:** 16\ **Page:** 1
**Author:** ![gchandel6](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@gchandel6](https://discuss.codechef.com/u/gchandel6)\ **Post date:** [September 17, 2014, 6:37am UTC](https://discuss.codechef.com/t/finding-longest-path-in-an-undirected-and-unweighted-graph/7160/1 "2014-09-17T06:37:55Z")
please someone help , i just cant find a way to find THE LONGEST PATH IN AN UNDIRECTED AND UNWEIGHTED GRAPH please , every where it is given that using bfs or dfs , but how bfs can solve this problem , can anybody explain, actually i have solved only 1 or 2 graph problems thats why iam unable to code this , can someone explain ??? ---
**Author:** ![japoorv](https://discuss.codechef.com/user_avatar/discuss.codechef.com/japoorv/32/3653_2.png) [@japoorv](https://discuss.codechef.com/u/japoorv)\ **Post date:** [September 17, 2014, 9:25am UTC](https://discuss.codechef.com/t/finding-longest-path-in-an-undirected-and-unweighted-graph/7160/2 "2014-09-17T09:25:19Z")
What are you really looking for longest path from a specific node or overall longest path ---
**Author:** ![rajeevkgprk](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@rajeevkgprk](https://discuss.codechef.com/u/rajeevkgprk)\ **Post date:** [September 17, 2014, 10:17am UTC](https://discuss.codechef.com/t/finding-longest-path-in-an-undirected-and-unweighted-graph/7160/3 "2014-09-17T10:17:38Z")
1. Use a weight variable to store weight of the corresponding nodes. 2. Use bfs on any node(e.g. node no. 1) to find the node located farthest from the node(from node no. 1). You can do this by assigning 0 to the node( node no. 1) and then in every iteration assign the current nodes, one greater number than the node whose edge the current nodes are.( weight of current node = weight of parent node +1) 3. Use a visit variable to mark the visited nodes so that you don’t visit them again. 4. Iterate over every node to find the node with highest number. 5. Reallocate the weight and visit array variable to 0 and again use bfs from node found in last step to find the node located farthest from this node. ---
**Author:** ![gastonfontenla](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@gastonfontenla](https://discuss.codechef.com/u/gastonfontenla)\ **Post date:** [January 24, 2016, 2:22pm UTC](https://discuss.codechef.com/t/finding-longest-path-in-an-undirected-and-unweighted-graph/7160/4 "2016-01-24T14:22:51Z")
Maybe you could try with DFS from each node, or with Floyd-Warshall algorithm. Depend on the input. ---
**Author:** ![thedark](https://discuss.codechef.com/user_avatar/discuss.codechef.com/thedark/32/14008_2.png) [@thedark](https://discuss.codechef.com/u/thedark)\ **Post date:** [January 24, 2016, 5:28pm UTC](https://discuss.codechef.com/t/finding-longest-path-in-an-undirected-and-unweighted-graph/7160/5 "2016-01-24T17:28:14Z")
You can practice this ([SPOJ.com - Problem PT07Z](http://www.spoj.com/problems/PT07Z/)) problem for a better understanding of the algorithm given by @rajeevkgprk ---
**Author:** ![jd\_tc](https://discuss.codechef.com/user_avatar/discuss.codechef.com/jd_tc/32/6130_2.png) [@jd\_tc](https://discuss.codechef.com/u/jd_tc)\ **Post date:** [January 8, 2019, 12:38pm UTC](https://discuss.codechef.com/t/finding-longest-path-in-an-undirected-and-unweighted-graph/7160/6 "2019-01-08T12:38:03Z")
I don’t think this problem can be solved using BFS, but only through DFS. @rajeevkgprk ---
**Author:** ![gchandel6](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@gchandel6](https://discuss.codechef.com/u/gchandel6)\ **Post date:** [September 17, 2014, 10:25am UTC](https://discuss.codechef.com/t/finding-longest-path-in-an-undirected-and-unweighted-graph/7160/7 "2014-09-17T10:25:03Z")
overall longest path but the main problem is to find the distance from two nodes in a graph I can use bfs twice to find the farthest nodes in the graph , but now how to find distance between them ---
**Author:** ![gchandel6](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@gchandel6](https://discuss.codechef.com/u/gchandel6)\ **Post date:** [September 17, 2014, 10:26am UTC](https://discuss.codechef.com/t/finding-longest-path-in-an-undirected-and-unweighted-graph/7160/8 "2014-09-17T10:26:36Z")
yes , i have done this i have found the farthest node in the graph (by using bfs twice) but now how to find the distance between them?? ---
**Author:** ![rajeevkgprk](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@rajeevkgprk](https://discuss.codechef.com/u/rajeevkgprk)\ **Post date:** [September 17, 2014, 10:30am UTC](https://discuss.codechef.com/t/finding-longest-path-in-an-undirected-and-unweighted-graph/7160/9 "2014-09-17T10:30:36Z")
It will simply be the weight of farthest found node. because the weight of node on which you began bfs was initialized to 0 ---
**Author:** ![gchandel6](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@gchandel6](https://discuss.codechef.com/u/gchandel6)\ **Post date:** [September 17, 2014, 8:19pm UTC](https://discuss.codechef.com/t/finding-longest-path-in-an-undirected-and-unweighted-graph/7160/10 "2014-09-17T20:19:03Z")
but this is an unweighted graph ---
**Author:** ![rajeevkgprk](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@rajeevkgprk](https://discuss.codechef.com/u/rajeevkgprk)\ **Post date:** [September 17, 2014, 9:27pm UTC](https://discuss.codechef.com/t/finding-longest-path-in-an-undirected-and-unweighted-graph/7160/11 "2014-09-17T21:27:56Z")
Of course it is an un-weighted graph. Please do not misunderstand the use of array ‘weight[]’ here. It is used to calculate the distance between nodes. The weight of every node is one more than the weight of its previous connected node’s weight since it is an un-weighted graph, otherwise it would be weight of previous node + weight of the edge. This way you can find the farthest located node by its weight. I hope I am clear. ---
**Author:** ![gchandel6](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@gchandel6](https://discuss.codechef.com/u/gchandel6)\ **Post date:** [September 22, 2014, 12:00pm UTC](https://discuss.codechef.com/t/finding-longest-path-in-an-undirected-and-unweighted-graph/7160/12 "2014-09-22T12:00:39Z")
thanks sir , can you give me your facebook id , i have to ask many more doubts! ---
**Author:** ![rajeevkgprk](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@rajeevkgprk](https://discuss.codechef.com/u/rajeevkgprk)\ **Post date:** [January 28, 2015, 9:59am UTC](https://discuss.codechef.com/t/finding-longest-path-in-an-undirected-and-unweighted-graph/7160/13 "2015-01-28T09:59:25Z")
[gchandel6](http://www.codechef.com/users/gchandel6) instead you can send a message [here](http://www.hackerearth.com/users/rajeev6) or [there](http://codeforces.com/profile/rajeevkgp) ---
**Author:** ![jd\_tc](https://discuss.codechef.com/user_avatar/discuss.codechef.com/jd_tc/32/6130_2.png) [@jd\_tc](https://discuss.codechef.com/u/jd_tc)\ **Post date:** [January 9, 2019, 12:01am UTC](https://discuss.codechef.com/t/finding-longest-path-in-an-undirected-and-unweighted-graph/7160/14 "2019-01-09T00:01:12Z")
BFS is useful in case of a tree. ---
**Author:** ![ecem](https://discuss.codechef.com/user_avatar/discuss.codechef.com/ecem/32/15834_2.png) [@ecem](https://discuss.codechef.com/u/ecem)\ **Post date:** [May 20, 2020, 12:53pm UTC](https://discuss.codechef.com/t/finding-longest-path-in-an-undirected-and-unweighted-graph/7160/15 "2020-05-20T12:53:03Z")
how did you use bfs twice and found the longest path, i am having the same problem ---
**Author:** ![spaanse](https://discuss.codechef.com/user_avatar/discuss.codechef.com/spaanse/32/214887_2.png) [@spaanse](https://discuss.codechef.com/u/spaanse)\ **Post date:** [July 23, 2020, 11:27am UTC](https://discuss.codechef.com/t/finding-longest-path-in-an-undirected-and-unweighted-graph/7160/17 "2020-07-23T11:27:49Z")
The algorithm you mention is for finding the diameter of the graph. For trees the diameter of the graph is equal to the length of the longest path, but for general graphs it is not. The general [longest path problem](https://en.wikipedia.org/wiki/Longest_path_problem) is NP-hard, so it is unlikely that anyone has found an algorithm to solve that problem in polynomial time.