longest path

Question

how can we find longest path between any pair of vertices in a garph??

Answer 1

The longest path problem is the problem to find the longest simple path between pair of vertices. 

A path is simple if vertices are not repeated in the path , otherwise the path length can be ifinite.

And the longest path problem is NP hard problem cannot be solved in polynomial, but for directed acyclic graph , 

it can be solved.

Link :  http://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/ 

If you can't understand the above algorithm then feel free to ask your queries.

And  one more method for DAG   is to convert all weight of edges to negative and then apply Bellman-Ford  algorithm ( But works only when there are no negative weight cycle present )   but graph is directed acyclic we can use Bellman-Ford .

For other type of graph like undirected, we can use dynamic programming approach with recursion like DFS/BFS

Everytime we just update the node ajacent to the current node only when the current_cost_on_node + edge-weight is greater then the oldest cost on adjacent node,  then so on... till the recursion end.

But it will work only in case of no cycle and graph is not so big , because its complexity is little much high. 

Comments

how are longest path and diameter of a graph different??

---

No, we don't relax any node atmost one.

we will update nodes till updation will be possible.

Example,    Let's take a graph of 3 nodes ( directed or undirected )

Let say directed.

edges : [ 1  -  2 ]  , [  1 - 3 ]  , [ 3 - 2 ]

cost  :        5                  2            2

edge 1 - > 2  have cost : 5 , second edge have cost 2 and third edge have cost 2

Suppose source node is 1 and destination is 2 ,

then their are two paths between 1 and 2

Path1 :  [1 - 2 ]   cost = 5

Path2 : [ 1 - 3 - 2 ]  cost = 2 + 2 = 4

When your start dijkstra's algo  and say you are considering edge [1-2] first , then you will make cost of node 1 : 0  ( source ) and relax node 2  and make the cost from infinit to 5 ,

then you make relax 3 node with cost 2  , and in future , node 3 relax node 2 , with cost 4 .

Here node 2 is no more relaxing atmost one time.

---

i meant every edge is relaxed exactly once..am i wrong?..:-(