All the possible path between two points without repetition

4 visualizzazioni (ultimi 30 giorni)
MarshallSc il 26 Feb 2022
Commentato: MarshallSc il 27 Feb 2022
I'm looking to get the value of all pairwise data between two points by an iteration. The iteration contains direct and indirect paths. For example if there are 3 points, and having all the pairwise scores between points being available:
a_11 = 0; a_12 = 0.2; a_13 = 0.6; a_32 = -0.3; % a_23 = -a_32 (same for all other scores)
Now if the value for example, the path between 1-2 is considered, we would have (direct + indirect):
a_12_iter1 = a_12 + (a_13 + a_32)% initial paiwsie scores between all points are known, a_12_iter1 means the first iteration
%considering the initial pairwise scores.
a_12_iter1 = 0.2 + (0.6 - 0.3) = 0.5
No path is chosen twice.
Another example is having 4 points (square):
a_12_iter1 = a_12 + (a_14 + a_43 + a_32 + a_13);
a_13_iter1 = a_13 + (a_12 + a_23 + a_14 + a_43 + a_24); %same procedure is used for all other values (a_14, a_24, ...)
The data gets large fast, another instant is a pentagon (5 points):
a_13_iter1 = a_13 + (a_12 + a_23 + a_15 + a_54 + a_43 + a_43 + a_25 + a_53 + a_14)% no path is chosen twice
I am looking for a code that can perform this operation if my original data is large (100 points). The code for 3 points is given as:
Does anyone know how I can write this code? Thank you!
0 CommentiMostra -2 commenti meno recentiNascondi -2 commenti meno recenti

Accedi per commentare.

Risposta accettata

Abolfazl Chaman Motlagh il 26 Feb 2022
You can solve this problem with your data as a matrix, or as a graph. the matrix make it easier i guess:
a traditional method with loop is kinnda this:
Connections = [0 0.2 0.6; -0.2 0 0.3; -0.6 -0.3 0]; % for 3 point problem
Path = zeros(3);
for i=1:3
for j=1:3
Path(i,j) = Connections(i,j); % First Term
for k=setdiff((1:3),[i,j])
Path(i,j) = Path(i,j) + Connections(i,k) + Connections(k,j);
end
end
end
Path
Path = 3×3
0 0.5000 1.1000 -0.5000 0 0.7000 -1.1000 -0.7000 0
you can see it is what you wanted.
of course inner loop can be vectorize to code below:
for i=1:3
for j=1:3
k=setdiff((1:3),[i,j]);
Path(i,j) = Connections(i,j) + sum(Connections(i,k)) + sum(Connections(k,j));
end
end
Path can also be initialize from Connections itself instead of zeros.
this can be your function for whatever velue and number of points you have.
function Path = Path_value_cal(Connections)
n = size(Connections);
Path = Connections;
for i=1:n
for j=1:n
k=setdiff((1:n),[i,j])
Path(i,j) = Path(i,j) + sum(Connections(i,k)) + sum(Connections(k,j));
end
end
end
1 CommentoMostra -1 commenti meno recentiNascondi -1 commenti meno recenti
MarshallSc il 27 Feb 2022
Thanks a lot mate!

Accedi per commentare.

Categorie

Scopri di più su Graph and Network Algorithms in Help Center e File Exchange

Community Treasure Hunt

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

Start Hunting!

Translated by