Selecting the shorted path between two nodes with prioritized edges

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 Kommentare

So you're saying you want some way to break ties among the shortest distance paths in a graph?
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 am 6 Mär. 2023
Bearbeitet: Matt J am 6 Mär. 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.

Melden Sie sich an, um zu kommentieren.

Antworten (1)

Matt J
Matt J am 6 Mär. 2023
Bearbeitet: Matt J am 6 Mär. 2023
EdgeTable = table(EndNodes,1+Edge_value/1e5,'Var',{'EndNodes', 'Weight'});

Kategorien

Mehr zu Graph and Network Algorithms finden Sie in Hilfe-Center und File Exchange

Gefragt:

am 6 Mär. 2023

Bearbeitet:

am 6 Mär. 2023

Community Treasure Hunt

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

Start Hunting!

Translated by