Selecting the shorted path between two nodes with prioritized edges

12 visualizzazioni (ultimi 30 giorni)
I have a graph, made up of 20 nodes, however, I want the edges to be prioritized into: first, seondary and tertiary, and have values assigned to them, and the value should be selected from the given range in random so when the graph is plotted, and I want to choose the shortest path between 2 nodes, it'll not only be based on crossing the shortest distance, but it'll take the edges' values into consideration too and choose the path that is the shortes with the least amounth of edges values summed simultaneously.
For example, if I want to go from node 13 to 9, the result should be: 13 - 14 - 15 - 12 - 11 - 10 - 9
I've tried a few ways, like setting a matrix and creating a loop to combine the edge values, or tried to set these values as edge weights and put in the graph, but nothing seems to work.
Is there any code that can get this done for me?
I've put the code I have so far for the the graph:
Exw = randi([70,85],1,1)/10; %first
MR = randi([56,70],1,1)/10; %secondary
SR = randi([36,56],1,1)/10; %tertiary
s = [1 1 1 1 2 2 2 3 3 3 4 4 5 5 5 7 8 9 10 11 12 13 13 14 16 16 17 18 19];
t = [2 4 14 16 5 19 3 6 7 20 5 12 6 11 8 8 9 10 11 12 15 14 16 15 17 18 19 19 20];
EndNodes = [s' t'];
Edge_value = [Exw; SR; MR; Exw; Exw; MR; MR; MR; MR; SR; MR; MR; SR; MR; Exw; MR; Exw; SR; MR; SR; MR; MR; MR; Exw; MR; MR; MR; SR; MR];
EdgeTable = table(EndNodes);
names = {'1'; '2'; '3'; '4'; '5'; '6'; '7'; '8'; '9'; '10'; '11'; '12'; '13'; '14'; '15'; '16'; '17'; '18'; '19'; '20'};
NodeTable = table(names);
G = graph(EdgeTable,NodeTable);
plot(G)
  3 Commenti
Elmira Haddadi
Elmira Haddadi il 6 Mar 2023
I suppose... well more precisely, I want more than one variable to be at play when it comes to choosing the shortest path. I'm not sure what I want can be considered as breaking ties among the shortest paths.
Imagine it like this: You want to drive from point A to B. The practical choice for a path is the one that is the shortest while having the least traffic at the same time. Now, apply it to the code, how to make the stimulation choose a path that has the shortest distance while having the least traffic (the least value assigned to the edges).
Matt J
Matt J il 6 Mar 2023
Modificato: Matt J il 6 Mar 2023
The practical choice for a path is the one that is the shortest while having the least traffic at the same time.
That is surely what a driver would desire, but no such path may exist. The path with the least traffic may not be the shortest in distance. In that case, you need to define some sort of compromise criterion.

Accedi per commentare.

Risposte (1)

Matt J
Matt J il 6 Mar 2023
Modificato: Matt J il 6 Mar 2023
EdgeTable = table(EndNodes,1+Edge_value/1e5,'Var',{'EndNodes', 'Weight'});

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