Choose between 2 routes

2 visualizaciones (últimos 30 días)
Athos Garcia
Athos Garcia el 23 de Oct. de 2017
Comentada: Walter Roberson el 23 de Oct. de 2017
Hi guys,
I'm trying to find the shortest path between 2 points using the 'bwdistgeodesic' function. But sometimes it has more than 1 possible path and I don't know how to get all the routes separatelly.
Here is my code:
BW = [
1 1 1 0 0 0 0 0 0 0
1 0 1 1 0 0 0 0 1 1
1 1 0 1 1 1 0 0 1 1
1 0 1 0 1 1 0 0 1 1
0 0 1 0 0 1 0 0 1 0
0 0 1 1 0 1 0 1 1 0
0 1 0 1 1 1 0 0 0 0
0 0 1 1 1 1 1 0 1 0
0 0 1 0 0 0 0 1 1 0
0 0 0 0 1 0 0 0 0 0
];
BW = logical(BW);
p1 = [1 1];
p2 = [9 8];
D1 = bwdistgeodesic(BW, p1(1), p1(2), 'quasi-euclidean');
D2 = bwdistgeodesic(BW, p2(1), p2(2), 'quasi-euclidean');
pth = D1 + D2;
c = [];
[c(:,1), c(:,2)] = find(abs(pth - pth(C(1), R(1))) < 1e-3);
figure, hold on
imagesc(BW), axis image, colormap gray, axis off
plot(c(:,2), c(:,1), 'r*', 'MarkerSize', 5)
hold off
For this sample I know that are 2 routes:
figure, hold on
imagesc(BW), axis image, colormap gray, axis off
plot(c(:,2), c(:,1), 'r*', 'MarkerSize', 5)
ics1 = [1 3 5 8 10 12 13 14 16:18];
ics2 = [1 2 4 6 7 9 11 15:18];
plot(c(ics1,2), c(ics1,1), c(ics2,2), c(ics2,1))
But how do I get the indexes 'ics1' and 'ics2' automatically?
  1 comentario
Walter Roberson
Walter Roberson el 23 de Oct. de 2017
There was a recent question explained at https://www.mathworks.com/matlabcentral/answers/360917-shortest-path-between-two-nodes-in-unweighted-graph#comment_492199 in which the person asking wanted to find all of the shortest paths between two nodes. Unfortunately no-one has contributed a solution. I have not managed to think of a solution that is not essentially a breadth-first search that was not to be terminated until all paths at the same depth were explored, with all of the paths to be returned.
Consider for example the grid,
A+++++++++
++++++++++
++++++++++
++++++++++
+++++++++B
If we take the case where diagonal moves are not permitted, then every node is part of at least two shortest paths:
  1. continue horizontally until you reach the right column, then go down the column to the node, then go horizontally from there to the last column, then go down from there to the target; and
  2. go down until you reach the right row, then go horizontally until you reach the node, then go down from there until you reach the last row, then go horizontally from there to each the target.
You can easily extend this to another two paths for most locations: go horizontally until you reach the right column, go vertically all the way to the bottom passing through the node, go horizontally to the target; or go down until you reach the right row, go horizontally all the way to the last column passing through the node, go vertically down to the target.
And clearly there are a lot of other paths that go through any given node. The algorithm would have to be able to return all of them. The number of such paths would be nchoosek(number_of_down+number_of_right, number_of_down) which is the same as nchoosek(number_of_down+number_of_right, number_of_right). In the example diagram it would be nchoosek(9+4,4) = 715 different paths.

Iniciar sesión para comentar.

Respuestas (0)

Categorías

Más información sobre Colormaps en Help Center y File Exchange.

Community Treasure Hunt

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

Start Hunting!

Translated by