# Optimise vertical position of nodes for shortest sum of paths

1 view (last 30 days)

Show older comments

Hi, I am doing a project which aims to optimise the layout of nodes.

I have a matrix of many paths. Each row of the matrix is a separate path. Each path specifies through which nodes a path has to go from start to finish.

MATRIX OF PATHS = [a b c d e; a b d e g; a c b e g; a b c f; a b c d; a b c d e; a b d e; a b c f g]

Each of these nodes has an assigned x coordinate, however, the y coordinate has to be chosen in the most optimal way. The y coordinate has to be an integer that is equal to or greater than 1, so: (1,2,3,4...). The most optimal way is such that minimises the total length of paths.

LIST OF NODES: a: x=1 b: x=2 c: x=3 d: x=3 e: x=4 f: x=4 g: x=5

##### 2 Comments

### Answers (2)

Bjorn Gustavsson
on 28 Oct 2022

If this is a one-off calculation just brute-force search shouldn't be too bad, the y-position of the nodes should be within a small range of integer values spanning no more than 7, you have seven y-values to search for. This makes the maximum combinations to look through 7^7, check that they fullfill your condition of notoverlapping and then calculate the total distances and keep those shorter than or equal to the currently shortest. No need to think or read up on an efficient integer-programming optimization algorithm that will take far longer time. Something like this to get you started:

shortest_total_path = inf;

for a = 1:7

for b = 1:7

for c = 1:7

for d = 1:7

for e = 1:7

for f = 1:7

for g = 1:7

Paths = {[[a;1], [b;2], [c;3], [d;3], [e;4]],...

[[a;1], [b;2], [d;3], [e;4], [g;5]],...

[[a;1], [c;3], [b;2], [e;4], [g;5]],...

[[a;1], [b;2], [c;3], [f;4]],...

[[a;1], [b;2], [c;3], [d;3]],...

[[a;1], [b;2], [c;3], [d;3], [e;4]],...

[[a;1], [b;2], [d;3], [e;4]],...

[[a;1], [b;2], [c;3], [f;4], [g;5]]};

% Calculate sum of the lengths of the paths

% save the total length in an array of with all lengths

% compare to currently shortest

% save this path if it is shorter

end

end

end

end

end

end

end

If on the other hand this is a problem where you will have to solve this type of tasks many times over you'll have to read up on efficient algorithms.

HTH

Steven Lord
on 28 Oct 2022

### See Also

### Categories

### Community Treasure Hunt

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

Start Hunting!