Find the longest path in a graph?
34 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
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 comentarios
Respuestas (2)
Massimo Zanetti
el 9 de Oct. de 2016
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 comentarios
Ivan
el 14 de Dic. de 2017
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 comentario
MICHAEL MONT-ETON
el 29 de Nov. de 2020
Ivan, Thanks for the tip. It is useful for finding collection of independent paths.
Ver también
Categorías
Más información sobre Construction en Help Center y File Exchange.
Productos
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!