LONGEST PATH BY PRODUCT

3 views (last 30 days)
Lala
Lala on 12 Jan 2020
Commented: Lala on 26 Jan 2020
Hello,
I have an adjacency matrix (A= [0,0,0.6,0.7,0.3;0.9,0,0,0.3,0;0,0.6,0,0.9,0;0,0,0.4,0,0.9;0,0,0,0,0]) that represents the weights of edges on a 5 node graph, and I wish to find the longest (by product not sum) between two nodes. I was considering doing an element by element inverse of the matrix (1./A) then I would go ahead and apply the Dijkstra's algorithm but using this method would give me the longest path (due to the inverse funtion) based on summation, where as I need the longest path based on multiplication.
  2 Comments
Lala
Lala on 26 Jan 2020
Thank you

Sign in to comment.

Accepted Answer

Thiago Henrique Gomes Lobato
You can take the log of your inverse matrix and use the log property:
Which basically says that maximizing/minimizing the sum (of logs) is the same as maximizing/minimizing the product of the variables.

More Answers (0)

Community Treasure Hunt

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

Start Hunting!

Translated by