List of paths between two points

I have a list of "Start point" and "End point", and I want to find all shortest paths between a point (let's say the first one) and every other point, there is maximum steps to avoid infinit looping.

Shortly, what I do now is creating a matrix by duplicating all single paths up to the "maximum steps" value, and then looping on steps then selecting for every "End Point" the lines that end with it (the end point) if exists.

For a list of 2^6 * 7 elements, there's 7^6 lines on the resulted matrix, but for 2^n * (n+1) there's n^(n+1) lines. I understand that this is sligntly analogic to the travelling salesman problem, but I just want to know if there's a more economic process to do this. and I only need it to run to the n=20, now I can's go further 6

here's my sample data. Thanks

Answer 1

[Walter Roberson]

https://www.mathworks.com/help/matlab/ref/graph.shortestpathtree.html

TR = shortestpathtree(G,s) returns a directed graph, TR, that contains the tree of shortest paths from source node s to all other nodes in the graph. If the graph is weighted (that is, G.Edges contains a variable Weight), then those weights are used as the distances along the edges in the graph. Otherwise, all edge distances are taken to be 1.

[rachid rachid]

I am not familiar with the graphs, so it might sound dunb but, in my case what would be the edges and the nodes ?

[Walter Roberson]

The start points and end points and other distinguished points would be the nodes. The connections between them would be the edges.

For example if you have two cities that are of interest, then those would be nodes, and if you abstract away the road between them to just a distance number and the fact that the road exists, then the connection would be edges.

Intersections are always nodes -- stopping points or switching points. Things you travel along are edges.

[rachid rachid]

Thank you very much, this is the code for the example data, if this can be of help to anyone

s = [1	1	1	1	1	1	1	2	2	2	2	2	2	2	3	3	3	3	3	3	3	4	4	4	4	4	4	4	5	5	5	5	5	5	5	6	6	6	6	6	6	6	7	7	7	7	7	7	7	8	8	8	8	8	8	8	9	9	9	9	9	9	9	10	10	10	10	10	10	10	11	11	11	11	11	11	11	12	12	12	12	12	12	12	13	13	13	13	13	13	13	14	14	14	14	14	14	14	15	15	15	15	15	15	15	16	16	16	16	16	16	16	17	17	17	17	17	17	17	18	18	18	18	18	18	18	19	19	19	19	19	19	19	20	20	20	20	20	20	20	21	21	21	21	21	21	21	22	22	22	22	22	22	22	23	23	23	23	23	23	23	24	24	24	24	24	24	24	25	25	25	25	25	25	25	26	26	26	26	26	26	26	27	27	27	27	27	27	27	28	28	28	28	28	28	28	29	29	29	29	29	29	29	30	30	30	30	30	30	30	31	31	31	31	31	31	31	32	32	32	32	32	32	32	33	33	33	33	33	33	33	34	34	34	34	34	34	34	35	35	35	35	35	35	35	36	36	36	36	36	36	36	37	37	37	37	37	37	37	38	38	38	38	38	38	38	39	39	39	39	39	39	39	40	40	40	40	40	40	40	41	41	41	41	41	41	41	42	42	42	42	42	42	42	43	43	43	43	43	43	43	44	44	44	44	44	44	44	45	45	45	45	45	45	45	46	46	46	46	46	46	46	47	47	47	47	47	47	47	48	48	48	48	48	48	48	49	49	49	49	49	49	49	50	50	50	50	50	50	50	51	51	51	51	51	51	51	52	52	52	52	52	52	52	53	53	53	53	53	53	53	54	54	54	54	54	54	54	55	55	55	55	55	55	55	56	56	56	56	56	56	56	57	57	57	57	57	57	57	58	58	58	58	58	58	58	59	59	59	59	59	59	59	60	60	60	60	60	60	60	61	61	61	61	61	61	61	62	62	62	62	62	62	62	63	63	63	63	63	63	63	64	64	64	64	64	64	64];
t = [58	59	60	61	62	63	64	32	31	30	28	24	64	63	25	26	27	29	64	24	62	21	22	23	64	29	28	61	19	20	64	23	27	30	60	18	64	20	22	26	31	59	64	18	19	21	25	32	58	45	46	47	41	37	36	57	43	44	41	47	35	38	56	42	41	44	46	34	39	55	41	42	43	45	33	40	54	39	40	37	35	47	42	53	38	37	40	34	46	43	52	37	38	39	33	45	44	51	36	35	34	40	44	45	50	35	36	33	39	43	46	49	34	33	36	38	42	47	48	6	7	57	56	53	48	47	5	57	7	55	52	49	46	57	5	6	54	51	50	45	4	56	55	7	50	51	44	56	4	54	6	49	52	43	55	54	4	5	48	53	42	54	55	56	57	2	3	41	3	53	52	50	7	54	40	53	3	51	49	6	55	39	52	51	3	48	5	56	38	51	52	53	2	57	4	37	50	49	48	3	4	57	36	49	50	2	53	56	5	35	48	2	50	52	55	6	34	2	48	49	51	54	7	33	63	17	16	14	11	58	32	17	63	15	13	10	59	31	16	15	63	12	9	60	30	15	16	17	62	61	8	29	14	13	12	63	8	61	28	13	14	62	17	60	9	27	12	62	14	16	59	10	26	62	12	13	15	58	11	25	11	10	9	8	63	62	24	10	11	61	60	17	12	23	9	61	11	59	16	13	22	61	9	10	58	15	14	21	8	60	59	11	14	15	20	60	8	58	10	13	16	19	59	58	8	9	12	17	18	31	32	29	27	23	18	17	30	29	32	26	22	19	16	29	30	31	25	21	20	15	28	27	26	32	20	21	14	27	28	25	31	19	22	13	26	25	28	30	18	23	12	24	23	22	20	32	25	11	23	24	21	19	31	26	10	22	21	24	18	30	27	9	20	19	18	24	28	29	8	1	47	46	44	40	33	7	47	1	45	43	39	34	6	46	45	1	42	38	35	5	44	43	42	1	36	37	4	40	39	38	36	1	41	3	33	34	35	37	41	1	2	7	6	5	4	3	2	1];
G = graph(s,t);
TR = shortestpathtree(G,1);
p = plot(TR);
TR{54} % Show the path to the 54th point

Answer 2

[Thiago Henrique Gomes Lobato]

It is not so clear by your list what underlying process you have, but I may assume you have a map (graph) where each point is a node and the nodes are connect by some distance metric (edge) and you want to find the way that minimizes that metric. This is basically a description of a path finding problem. For it there exist some algorithms that do it relatively efficiently as the Dijkstra or A*, they will surely be more memory and time efficient as to list all possible paths .

Here are some links that I founded in file exchange for matlab implementations (I didn't test myself, but should at least give you a direction):

https://de.mathworks.com/matlabcentral/fileexchange/36140-dijkstra-algorithm

https://de.mathworks.com/matlabcentral/fileexchange/56877-astar-algorithm