shortestpath

유방향 그래프를 생성하고 플로팅합니다.

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 사이의 최단 경로를 구하고 경로의 길이를 반환할 2개의 출력값도 지정합니다.

[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')

다중 그래프에서 두 노드 사이의 최단 경로를 플로팅하고, 최단 경로가 통과하는 특정 간선을 강조 표시합니다.

5개의 노드가 있는 가중 다중 그래프를 생성합니다. 몇몇 노드 쌍은 노드 쌍 사이에 둘 이상의 간선을 갖습니다. 참조 목적으로 그래프를 플로팅합니다.

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에 3개의 출력값을 지정하여 최단 경로가 통과하는 특정한 간선을 반환합니다.

[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 사이의 최단 경로를 계산하고 경로의 길이를 반환할 2개의 출력값도 지정합니다. 가중 그래프의 경우, 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)