Создайте и постройте ориентированного графа.

s = [1 1 2 3 3 4 4 6 6 7 8 7 5];
t = [2 3 4 4 5 5 6 1 8 1 3 2 8];
G = digraph(s,t);
plot(G)

Вычислите кратчайший путь между узлами 7 и 8.

P = shortestpath(G,7,8)

P = 1×5

     7     1     3     5     8

Создайте и постройте график с взвешенными ребрами.

s = [1 1 1 2 2 6 6 7 7 3 3 9 9 4 4 11 11 8];
t = [2 3 4 5 6 7 8 5 8 9 10 5 10 11 12 10 12 12];
weights = [10 10 10 10 10 1 1 1 1 1 1 1 1 1 1 1 1 1];
G = graph(s,t,weights);
plot(G,'EdgeLabel',G.Edges.Weight)

Найдите кратчайший путь между узлами 3 и 8 и задайте два выхода, чтобы также вернуть длину пути.

[P,d] = shortestpath(G,3,8)

P = 1×5

     3     9     5     7     8

d = 4

Поскольку края в центре графика имеют большие веса, самый короткий путь между узлами 3 и 8 обходит контур графика, где веса кромок наименьшие. Этот путь имеет общую длину 4.

Создайте и постройте график с взвешенными ребрами, используя пользовательские координаты узла.

s = [1 1 1 1 1 2 2 7 7 9 3 3 1 4 10 8 4 5 6 8];
t = [2 3 4 5 7 6 7 5 9 6 6 10 10 10 11 11 8 8 11 9];
weights = [1 1 1 1 3 3 2 4 1 6 2 8 8 9 3 2 10 12 15 16];
G = graph(s,t,weights);

x = [0 0.5 -0.5 -0.5 0.5 0 1.5 0 2 -1.5 -2];
y = [0 0.5 0.5 -0.5 -0.5 2 0 -2 0 0 0];
p = plot(G,'XData',x,'YData',y,'EdgeLabel',G.Edges.Weight);

Нахождение кратчайшего пути между узлами 6 и 8 на основе весов ребер графика. Выделите этот путь зеленым цветом.

[path1,d] = shortestpath(G,6,8)

path1 = 1×5

     6     3     1     4     8

d = 14

highlight(p,path1,'EdgeColor','g')

Задайте Method как unweighted игнорировать веса кромок, вместо этого обрабатывать все ребра так, как если бы они имели вес 1. Этот метод создает другой путь между узлами, который ранее имел слишком большую длину пути, чтобы быть самым коротким пути. Выделите этот путь красным цветом.

[path2,d] = shortestpath(G,6,8,'Method','unweighted')

path2 = 1×3

     6     9     8

d = 2

highlight(p,path2,'EdgeColor','r')

Постройте график кратчайшего пути между двумя узлами в мультиграфике и выделите определенные ребра, которые проходят.

Создайте взвешенный мультиграфик с пятью узлами. Несколько пар узлов имеют более одного ребра между ними. Постройте график для ссылки.

G = graph([1 1 1 1 1 2 2 3 3 3 4 4],[2 2 2 2 2 3 4 4 5 5 5 2],[2 4 6 8 10 5 3 1 5 6 8 9]);
p = plot(G,'EdgeLabel',G.Edges.Weight);

Найдите кратчайший путь между узлом 1 и узлом 5. Поскольку несколько пар узлов имеют более одного ребра между ними, задайте три выхода, чтобы shortestpath чтобы вернуть определенные ребра, по которым проходит кратчайший путь.

[P,d,edgepath] = shortestpath(G,1,5)

P = 1×5

     1     2     4     3     5

d = 11

edgepath = 1×4

     1     7     9    10

Результаты показывают, что самый короткий путь имеет общую длину 11 и следует по краям, заданным G.Edges(edgepath,:).

G.Edges(edgepath,:)

ans=4×2 table
    EndNodes    Weight
    ________    ______

     1    2       2   
     2    4       3   
     3    4       1   
     3    5       5   

Выделите это ребро пути при помощи highlight функция со 'Edges' Пара "имя-значение" для задания индексов пройденных кромок.

highlight(p,'Edges',edgepath)

Найдите кратчайший путь между узлами в графике, используя расстояние между узлами в качестве веса ребер.

Создайте графиков с 10 узлами.

s = [1 1 2 2 3 4 4 4 5 5 6 6 7 8 9];
t = [2 4 3 5 6 5 7 9 6 7 7 8 9 10 10];
G = graph(s,t);

Создайте координаты x и y для узлов графика. Затем постройте график с помощью координат узла путем определения 'XData' и 'YData' Пары "имя-значение".

x = [1 2 3 2 2.5 4 3 5 3 5];
y = [1 3 4 -1 2 3.5 1 3 0 1.5];
plot(G,'XData',x,'YData',y)

Добавьте веса кромок к графику путем вычисления евклидовых расстояний между узлами графика. Расстояние вычисляется из координат узла $\left({\mathit{x}}_{\mathit{i}},{\mathit{y}}_{\mathit{i}}\right)$ как:

Вычислять $\Delta \mathit{x}$ и $\Delta \mathit{y}$, первое использование findedges для получения векторов sn и tn описание исходного и целевого узлов каждого ребра в графике. Затем используйте sn и tn для индекса в векторы координат X и Y и вычисления $\Delta \mathit{x}={\mathit{x}}_{\mathit{s}}-{\mathit{x}}_{\mathit{t}}$ и $\Delta \mathit{y}={\mathit{y}}_{\mathit{s}}-{\mathit{y}}_{\mathit{t}}$. The hypot функция вычисляет квадратуру суммы квадратов, поэтому задайте $\Delta \mathit{x}$ и $\Delta \mathit{y}$ как входные параметры для вычисления длины каждого ребра.

[sn,tn] = findedge(G);
dx = x(sn) - x(tn);
dy = y(sn) - y(tn);
D = hypot(dx,dy);

Добавьте расстояния к графику в качестве весов ребер и повторите график с отмеченными ребрами.

G.Edges.Weight = D';
p = plot(G,'XData',x,'YData',y,'EdgeLabel',G.Edges.Weight);

Вычислите самый короткий путь между узлом 1 и узлом 10 и задайте два выхода, чтобы также вернуть длину пути. Для взвешенных графиков, shortestpath автоматически использует 'positive' метод, учитывающий веса кромок.

[path,len] = shortestpath(G,1,10)

path = 1×4

     1     4     9    10

len = 6.1503

Используйте highlight функция для отображения пути на графике.

highlight(p,path,'EdgeColor','r','LineWidth',2)