MATLAB: LONGEST PATH BY PRODUCT

adjacency matrixnp hard

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.

Best Answer

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.

Related Solutions

MATLAB: How to stop incidence function rearranging the edges of a graph

The reordering isn't happening when the incidence of the graph is computed, but instead at the moment that the graph is constructed: The graph and digraph classes always standardize the order of the edges, the original order isn't preserved in the object.

If you just need the incidence matrix based on s and t, and using original ordering, you can compute this directly:

nn = max([s(:); t(:)]); % number of nodes
ne = length(s); % number of edges
inc = sparse([s(:) t(:)], (1:ne)'*[1 1], ones(ne,1)*[-1 1], nn, ne);

If you need the graph itself, too, you can make the original order of the edges to be stored as the Weight variable in the graph's Edges table.

g = graph(s, t, 1:length(s)); % Verify that g.Edges.Weight contains the original placement of each edge in the (s, t) inputs
inc2 = incidence(g);
inc2(:, g.Edges.Weight) = inc2;
isequal(inc, inc2)

MATLAB: Tapering out a waveform.

The classic answer to this problem is to multiply the signal by a "window" such as the Hamming window, so if X is your signal.

 Y = X.*hamming(length(X));

You may have to transpose one of the vectors, hamming() returns a column vector.

However, the waveform you show above does not change much with tapering by a window.

Best Answer

Related Solutions

MATLAB: How to stop incidence function rearranging the edges of a graph

MATLAB: Tapering out a waveform.

Related Question