Find the longest path in a graph?

Adjacency matrix of graph is given to us. Now we need to find out the longest path between two nodes. Input: Adjacency matrix of the graph, source node and destination node. Output: Longest path between source node and destination node.

[Matt J]

Who is "we"? If you mean you and your classmates, show us your code and where in it you are stuck.

[Walter Roberson]

If there are any cycles then the longest path is infinite.

Answer 1

[Massimo Zanetti]

Generally this is NP-hard problem. However, for DAGs (directed acyclic graphs) there is one clever way to solve the problem. It is called "topological sorting". See details here or elsewhere in google: https://en.wikipedia.org/wiki/Topological_sorting

Answer 2

[Ivan]

Try to invert signs of weight coefficient and calculate shortest path with built-in shortestpath function. It will be the longest path for initial weights.

[MICHAEL MONT-ETON]

Ivan, Thanks for the tip. It is useful for finding collection of independent paths.