Find the longest path in a graph?

16 次查看（过去 30 天）
SOUMEN ATTA
SOUMEN ATTA 2012-10-29
评论： 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
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
Walter Roberson 2012-10-29
If there are any cycles then the longest path is infinite.

请先登录，再进行评论。

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

回答（2 个）

Massimo Zanetti
Massimo Zanetti 2016-10-9
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
Ivan
Ivan 2017-12-14
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.
  1 个评论
MICHAEL MONT-ETON
MICHAEL MONT-ETON 2020-11-29
Ivan, Thanks for the tip. It is useful for finding collection of independent paths.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Networks 的更多信息

标签

产品

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by