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

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}}$. 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)