Find the longest path in a graph?

Question

SOUMEN ATTA 2012-10-29

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/52208-find-the-longest-path-in-a-graph

评论： MICHAEL MONT-ETON 2020-11-29

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.

2 个评论
显示无隐藏无

Matt J 2012-10-29

编辑：Matt J 2012-10-29

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

Walter Roberson 2012-10-29

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

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Massimo Zanetti 2016-10-9

3
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/52208-find-the-longest-path-in-a-graph#answer_238199

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

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

Answer 2

Ivan 2017-12-14

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/52208-find-the-longest-path-in-a-graph#answer_296212

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.