A = [ 1 2 1;1 3 1;1 4 1;2 5 2;3 5 3;4 5 4] ; For above matrix first i need out put like all possible path like 1-2-5 and its total weight (1+2 =3); path 1-3-5 and its total weight (1+3 = 4), Path 1-4-5 and its total weight (1+4 =5);

Finding Longest Path in Directed Acyclic Graph

[KALYAN ACHARJYA]

What are the path represents? Matrix element values?

[DHARMAN J]

In each Row, First two element for connection between two nodes and third elements for its weight for that connection

Answer 1

[Magdy Saleh]

You can try this:

A = [ 1 2 1;1 3 1;1 4 1;2 5 2;3 5 3;4 5 4];

cntr = 1;
path = [];
for i = 1:length(A)
    path(i).startNode = A(i, 1);
    path(i).path = [A(i, 2)];
    path(i).weight = A(i, 3);
end

for i = 1:length(A)
    for j = 1:length(A)
        if(path(j).path(end) == A(i, 1))
            path(j).path = [path(j).path,  A(i, 2)];
            path(j).weight = path(j).weight +  A(i, 2);
        end
    end
end

But this assumes that your paths are at most of length two. Otherwise you might want to consider a recursive approach.

[DHARMAN J]

clc; clear all; close all; A = [ 1 2 0;1 8 0;1 5 0;1 3 0;1 4 0; 1 6 0;1 7 0;2 5 0.3;3 6 1.8;3 8 1.8; 4 7 0.3;5 9 0.9; 6 9 0.9; 7 9 0.9; 8 9 0.9]; cntr = 1 ; path = []; for i = 1:length(A ) path(i).startNode = A(i, 1 ); path(i).path = [A(i, 2 )]; path(i).weight = A(i, 3 ); end

for i = 1:length(A ) for j = 1:length(A ) if(path(j).path(end) == A(i, 1 )) path(j).path = [path(j).path, A(i, 2 )]; path(j).weight = path(j).weight + A(i, 3 ); end end end

For above code : The path is 1-3-8-9 path is missing sir and am not getting. please can you rectify this code sir.

[Magdy Saleh]

The above code depends on how deep your paths are.

[DHARMAN J]

Sir, Can you provide answer for below matrix A. A = [ 1 2 0;1 8 0;1 5 0;1 3 0;1 4 0; 1 6 0;1 7 0;2 5 0.3;3 6 1.8;3 8 1.8; 4 7 0.3;5 9 0.9; 6 9 0.9; 7 9 0.9; 8 9 0.9]

[Magdy Saleh]

clc;

A = [ 1 2 0;1 8 0;1 5 0;1 3 0;1 4 0; 1 6 0;1 7 0;2 5 0.3;3 6 1.8;3 8 1.8; 4 7 0.3;5 9 0.9; 6 9 0.9; 7 9 0.9; 8 9 0.9];

cntr = length(A)+1;
path = [];
for i = 1:length(A)
    path(i).startNode = A(i, 1);
    path(i).path = A(i, 2);
    path(i).weight = A(i, 3);
end

while(1)
    for i = 1:length(A)
        A(i, :)
        for j = 1:length(path)
            break_loop = 1;
            path(j)
            if(path(j).path(end) == A(i, 1))
                path(cntr).startNode = path(j).startNode;
                path(cntr).path = [path(j).path,  A(i, 2)];
                path(cntr).weight = path(j).weight +  A(i, 2);
                break_loop = 0;
                cntr = cntr +1;
            end
        end
    end
    if(break_loop)
        break 
    end
end

[DHARMAN J]

Sir, For Above A matrix, My expected path and its weight are: 1) 1-2-5-9 = 1.2; 2) 1-8-9 = 0.9; 3) 1-5-9 =0.9; 4)1-3-6-9 = 2.7; 5) 1-3-8-9 = 2.7; 6) 1-4-7-9 = 1.2; 7) 1-6-9 = 0.9; 8) 1-7-9 = 1.8; Like above output i need to display in Command Window. Please provide code for above path output and its weight sir. Thank you

[Magdy Saleh]

Just print out the path struct. It holds the weights in path.weight, the start in path.startNode and the path itself in path.path

[Guillaume]

Never use length with a matrix. The above code will error (index exceeds matrix dimension) if A is only two rows.

Note that matlab has functions to deal with graphs. In this case, digraph could be used to construct the graph. isdag could be used to check that the graph is indeed acyclic (otherwise the longest path is infinite), and toposort to get the hierarchy of the nodes.

There's several functions to find the shortest path of a graph but nothing for the longest path since that's a significantly harder problem (NP-hard). However, since the graph is supposed to be a DAG, there is a fairly simple algorithm as described on Wikipedia. I would recommend the OP implements that.

Note: to construct the graph from A:

g = digraph(A(:, 1), A(:, 2), A(:, 3));
%to visualise the graph:
plot(g, 'EdgeLabels', g.Edges.Weight)
%to find the topological ordering required for the wiki algorithm:
topo = toposort(g);

[DHARMAN J]

s = [1 1 1 1 1 1 2 3 3 4 5 6 7 8]; t = [2 8 4 7 5 3 5 6 8 7 9 9 9 9]; weights = [0 0 0 0 0 0 0.3 1.8 1.8 0.3 0.9 0.9 0.9 0.9]; G = digraph(s,t,weights); plot(G,'EdgeLabel',G.Edges.Weight);

The above code i done already but In command window, i need print the all path and its total weight for that graph (Source node = 1 & Destination Node = 9) and finally i need to print highest weight Path in the command window.

[Guillaume]

Please learn format your posts. Can't you see that my post is a lot more readable than yours.

"i need to print highest weight Path"

As said, you'll have to implement the algorithm described in the wikipedia article (or any better algorithm that you can find in a scientific paper). I haven't got the time to do that for you.

[DHARMAN J]

Hi sir, Thanks for reply. I couldn't implement such algorithms. S only posted here

[Guillaume]

I suggest you make a start at implementing and when you have a specific problem with it, come back and ask for help, showing what you have come up with so far.