shortestpathtree

노드의 최단 경로 트리

구문

TR = shortestpathtree(G,s)

TR = shortestpathtree(G,s,t)

TR = shortestpathtree(___,Name,Value)

[TR,D] = shortestpathtree(___)

[TR,D,E] = shortestpathtree(___)

설명

TR = shortestpathtree(G,s)는 소스 노드 s에서 그래프의 다른 모든 노드로 연결되는 최단 경로로 구성된 트리를 포함하는 유방향 그래프 TR를 반환합니다. 그래프가 가중 그래프(즉, G.Edges가 변수 Weight를 포함함)인 경우에는 가중치가 그래프에서 간선의 거리로 사용됩니다. 가중 그래프가 아닌 경우에는 모든 간선 거리가 1로 처리됩니다.

TR = shortestpathtree(G,s,t)는 여러 소스 노드나 타깃 노드 사이의 최단 경로로 구성된 트리를 계산합니다.

• s는 단일 소스 노드일 수 있으며, t는 여러 타깃 노드를 지정할 수 있습니다.

• s는 여러 소스 노드를 지정할 수 있으며, t는 단일 타깃 노드를 지정할 수 있습니다.

TR = shortestpathtree(___,Name,Value)는 위에 열거된 구문에 나와 있는 입력 인수의 조합과 함께, 하나 이상의 이름-값 쌍의 인수로 지정된 추가적인 옵션을 사용합니다. 예를 들어, shortestpathtree(G,s,'OutputForm','vector')는 최단 경로 트리를 설명하는 숫자형 벡터를 반환합니다.

[TR,D] = shortestpathtree(___)는 트리에서 노드 사이의 최단 경로 거리를 추가적으로 반환합니다.

[TR,D,E] = shortestpathtree(___)는 각 그래프 간선이 TR에 포함되는지 나타내는 논리형 벡터 E를 추가로 반환합니다.

예제

지정된 소스 노드에서의 최단 경로

소스 노드를 기준으로 하여 그래프에서 도달 가능한 기타 노드 각각에 대한 최단 경로를 구하고 결과를 플로팅합니다.

유방향 그래프를 생성합니다.

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)

G = 
  digraph with properties:

    Edges: [13x1 table]
    Nodes: [8x0 table]

노드 1을 기준으로 하여 그래프에서 도달 가능한 기타 노드 각각에 대한 최단 경로를 계산합니다. 그런 다음, 그래프 위에 결과로 생성된 트리를 플로팅합니다.

TR = shortestpathtree(G,1);
p = plot(G);
highlight(p,TR,'EdgeColor','r')

노드 1에서 노드 7로 연결되는 경로가 없으므로 노드 7에서 트리의 연결이 끊어집니다.

지정된 타깃 노드로의 최단 경로

그래프의 각 노드에서 타깃 노드로 연결되는 최단 경로를 구하고 결과를 플로팅합니다.

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

s = [1 1 1 1 1 1 1 2 2 7 7 7 7 9 9 3 3 1 6 4 8 10 6 8 4 5];
t = [2 3 4 5 6 8 7 6 7 5 6 8 9 6 8 6 10 10 10 10 10 11 11 11 8 8];
G = graph(s,t);
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];
plot(G,'XData',x,'YData',y)

그래프의 각 노드에서 노드 10으로 연결되는 최단 경로를 구합니다. 결과로 생성되는 트리를 플로팅합니다.

TR = shortestpathtree(G,'all',10);
plot(TR)

지정된 소스 노드를 사용한 최단 경로의 서브셋

단일 소스 노드에서 여러 타깃 노드로 연결되는 최단 경로와 경로 길이를 구합니다.

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

G = digraph(bucky);
plot(G)

노드 23에서 여러 다른 노드로 연결되는 최단 경로를 구합니다. OutputForm을 cell로 지정하여 셀형 배열로 최단 경로를 반환합니다. 최단 경로 거리를 반환할 두 출력값도 지정합니다.

target = [1 5 13 32 44];
[TR,D] = shortestpathtree(G,23,target,'OutputForm','cell')

TR=5×1 cell array
    {[         23 22 21 4 5 1]}
    {[           23 22 21 4 5]}
    {[23 22 20 16 17 15 14 13]}
    {[      23 22 20 19 18 32]}
    {[      23 24 48 47 46 44]}

D = 1×5

     5     4     7     5     5

tree{j}는 노드 23에서 노드 target(j)까지의 최단 경로이며 길이가 D(j)입니다.

노드 21에서 노드 5까지의 경로와 경로 길이를 구합니다.

path = TR{2}

path = 1×5

    23    22    21     4     5

path_length = D(2)

path_length = 4

입력 인수

G — 입력 그래프

graph 객체 | digraph 객체

입력 그래프로, graph 객체 또는 digraph 객체로 지정됩니다. 무방향 그래프를 생성하려면 graph를 사용하고 유방향 그래프를 생성하려면 digraph를 사용하십시오.

예: G = graph(1,2)

예: G = digraph([1 2],[2 3])

s — 소스 노드

노드 인덱스 | 노드 이름 | 'all'

소스 노드로, 하나 이상의 노드 인덱스 또는 노드 이름으로 지정되거나 'all'과 함께 사용되어 그래프의 모든 노드로 지정됩니다.

• 단독으로 사용할 경우 s는 단일 소스 노드를 지정해야 합니다.

• t와 함께 사용할 경우, s 입력값과 t 입력값은 다음을 충족해야 합니다.

  • s는 단일 소스 노드일 수 있으며, t는 여러 타깃 노드를 지정할 수 있습니다.

  • s는 여러 소스 노드를 지정할 수 있으며, t는 단일 타깃 노드를 지정할 수 있습니다.

다음 표에서는 숫자형 노드 인덱스 또는 노드 이름을 사용하여 하나 이상의 노드를 참조하는 몇 가지 방법을 보여줍니다.

형식	단일 노드	여러 노드
노드 인덱스	스칼라 예: 1	벡터 예: [1 2 3]
노드 이름	문자형 벡터 예: 'A'	문자형 벡터로 구성된 셀형 배열 예: {'A' 'B' 'C'}
	string형 스칼라 예: "A"	string형 배열 예: ["A" "B" "C"]

s는 'all'이라는 이름의 노드를 지정해서는 안 됩니다. 이 이름은 옵션 이름과 충돌하기 때문입니다. 이러한 경우에는 findnode를 사용하여 노드 인덱스를 전달하십시오.

예: shortestpathtree(G,'a')

예: shortestpathtree(G,[1 2 3],8)

t — 타깃 노드

'all' (디폴트 값) | 노드 인덱스 | 노드 이름

타깃 노드로, 하나 이상의 노드 인덱스 또는 노드 이름으로 지정되거나 'all'과 함께 사용되어 그래프의 모든 노드로 지정됩니다.

s 입력값과 t 입력값은 다음을 충족해야 합니다.

• s는 단일 소스 노드일 수 있으며, t는 여러 타깃 노드를 지정할 수 있습니다.

• s는 여러 소스 노드를 지정할 수 있으며, t는 단일 타깃 노드를 지정할 수 있습니다.

t는 'all', 'Method' 또는 'OutputForm'이라는 이름의 노드를 지정해서는 안 됩니다. 이러한 이름은 옵션 이름과 충돌하기 때문입니다. 이러한 경우에는 findnode를 사용하여 노드 인덱스를 전달하십시오.

예: shortestpathtree(G,[1 2 3],8)

예: shortestpathtree(G,{'a','b','c'},{'f'})

이름-값 인수

선택적 인수 쌍을 Name1=Value1,...,NameN=ValueN으로 지정합니다. 여기서 Name은 인수 이름이고 Value는 대응값입니다. 이름-값 인수는 다른 인수 뒤에 와야 하지만, 인수 쌍의 순서는 상관없습니다.

R2021a 이전 릴리스에서는 쉼표를 사용하여 각 이름과 값을 구분하고 Name을 따옴표로 묶으십시오.

예: [TR,D] = shortestpathtree(G,s,t,'Method','unweighted','OutputForm','vector')

OutputForm — 출력 형식

'tree' (디폴트 값) | 'cell' | 'vector'

출력 형식으로, 'OutputForm'과 함께 표에 나와 있는 옵션 중 하나가 쉼표로 구분되어 지정됩니다.

옵션	설명
'tree'(디폴트 값)	TR가 최단 경로 트리를 나타내는 유방향 그래프입니다. 이 옵션이 지정된 경우, 세 번째 출력 E는 각 간선이 TR에 포함되는지 나타내는 논리형 벡터입니다.
'cell'	TR가 셀형 배열이고, TR{k}가 s에서 t(k)로 또는 s(k)에서 t로 연결되는 경로를 포함합니다. 노드 사이에 경로가 없는 경우 TR{k}는 비어 있습니다. s와 t가 노드 이름인 경우 TR{k}는 문자형 벡터로 구성된 셀형 배열입니다. 그렇지 않은 경우, TR{k}는 숫자형 벡터입니다. 이 옵션이 지정된 경우, 세 번째 출력 E는 이에 대응하는 TR의 각 경로상의 간선을 나타내는 셀형 배열입니다.
'vector'	TR가 트리를 설명하는 벡터입니다. s가 단일 소스 노드를 포함하는 경우 TR(k)는 s에서 k로 연결되는 경로에서 노드 k 앞에 오는 노드의 ID입니다. 일반적으로, TR(s) = 0입니다. s가 여러 소스 노드를 포함하는 경우 TR(k)는 k에서 t로 연결되는 경로에서 노드 k 뒤에 오는 노드의 ID입니다. 일반적으로, TR(t) = 0입니다. 두 경우 모두, 노드 k가 트리의 일부가 아니면 TR(k)는 NaN입니다. 이 옵션이 지정된 경우, 세 번째 출력 E는 E(k)가 노드 k와 노드 TR(k)를 연결하는 최단 경로 트리의 간선 인덱스를 반환하는 벡터입니다.

예: shortestpathtree(G,s,'OutputForm','vector')

Method — 최단 경로 알고리즘

'auto' (디폴트 값) | 'unweighted' | 'positive' | 'mixed' | 'acyclic'

최단 경로 알고리즘으로, 'Method'와 함께 아래 표에 나와 있는 옵션 중 하나가 쉼표로 구분되어 지정됩니다.

옵션	설명
'auto'(디폴트 값)	'auto' 옵션은 다음과 같이 알고리즘을 자동으로 선택합니다. 간선 가중치가 없는 graph 입력값과 digraph 입력값에는 'unweighted'가 사용됩니다. 음수가 아닌 간선 가중치를 갖는 모든 graph 입력값에는 'positive'가 사용됩니다. 이 옵션은 음수가 아닌 간선 가중치를 갖는 digraph 입력값에도 사용됩니다. 음수 값을 일부 포함하는 간선 가중치를 갖는 digraph 입력값에는 'mixed'가 사용됩니다. 그래프는 음의 순환(Negative Cycle)을 가질 수 없습니다.
'unweighted'	모든 간선 가중치를 1로 처리하는 너비 우선 계산입니다.
'positive'	모든 간선 가중치가 음수가 아니어야 하는 데이크스트라 알고리즘(Dijkstra Algorithm)입니다.
'mixed'(digraph에만 해당)	그래프에 음의 순환을 허용하지 않는 유방향 그래프에 대한 벨만-포드 알고리즘(Bellman-Ford Algorithm)입니다. 'mixed'는 동일한 문제에 대해 'positive'보다 속도가 느리지만, 'mixed'는 일부 간선 가중치에 음수 값을 사용할 수 있으므로 더 유연합니다.
'acyclic'(digraph에만 해당)	가중치 간선이 있는 DAG(유방향 비순환 그래프)에 대한 성능을 향상시키도록 설계된 알고리즘입니다. 유방향 그래프가 비순환적(acyclic)인지 확인하려면 isdag를 사용하십시오.

참고

대부분의 그래프에 대해 'unweighted' 알고리즘이 가장 빠르며, 그 다음이 'acyclic', 'positive', 'mixed'순입니다.

예: shortestpath(G,s,t,'Method','acyclic')

출력 인수

TR — 최단 경로 트리

digraph 객체 (디폴트 값) | 셀형 배열 | 벡터

최단 경로 트리로, 'OutputForm'의 값에 따라 digraph 객체, 셀형 배열 또는 벡터로 반환됩니다. 그래프의 플롯 위에 최단 경로 트리를 시각화하려면 highlight 함수를 사용하고 자체적으로 최단 경로 트리를 시각화하려면 plot(TR)을 사용하십시오.

두 노드 사이에 최단 경로가 여러 개 있는 경우 TR는 이러한 경로 중 하나만 포함합니다. 반환되는 경로는 Method로 지정되는 알고리즘에 따라 바뀔 수 있습니다. 지정된 노드를 연결하는 경로가 없는 경우 TR 출력값은 간선이 없는 그래프입니다.

D — 소스 노드와 타깃 노드 사이의 거리

벡터

소스 노드와 타깃 노드 사이의 거리로, 벡터로 반환됩니다. Inf 값은 두 노드 사이에 경로가 없음을 나타냅니다.

E — 트리에 포함된 간선 또는 경로상의 간선

논리형 벡터 (디폴트 값) | 셀형 배열 | 벡터

트리에 포함된 간선 또는 경로상의 간선으로, 다음과 같이 'OutputForm'의 값에 따라 논리형 벡터, 셀형 배열 또는 벡터로 반환됩니다.

• 'OutputForm'을 지정하지 않거나 'tree'의 값을 지정한 경우, E는 각 그래프 간선이 유방향 그래프 TR에 포함되는지 나타내는 논리형 벡터입니다. 이 출력값은 highlight의 'Edges' 이름-값 쌍과 함께 사용할 수 있습니다(예: highlight(p,'Edges',E)).

• 'OutputForm'이 'cell'인 경우, E는 이에 대응하는 TR의 경로상의 간선을 포함하는 셀형 배열입니다.

• 'OutputForm'이 'vector'인 경우, E는 최단 경로 트리에서 각 노드를 부모 노드로 연결하는 간선의 인덱스를 반환하는 벡터입니다.

팁

• shortestpath, shortestpathtree, distances 함수는 음의 간선 가중치를 갖는 무방향 그래프를 지원하지 않으며, 더 일반적으로는 음의 순환을 포함하는 모든 그래프를 지원하지 않습니다. 그 이유는 다음과 같습니다.

  • 음의 순환은 노드에서 다시 자기 자신으로 연결되는 경로이며, 경로의 간선 가중치의 합이 음수가 됩니다. 음의 순환이 두 노드 사이의 경로에 있는 경우, 음의 순환을 순회하여 항상 더 짧은 경로를 발견할 수 있으므로 두 노드 사이에 최단 경로가 존재하지 않습니다.

  • 무방향 그래프에서 하나의 음의 간선 가중치는 하나의 음의 순환을 생성합니다.

확장 기능

스레드 기반 환경
MATLAB®의 backgroundPool을 사용해 백그라운드에서 코드를 실행하거나 Parallel Computing Toolbox™의 ThreadPool을 사용해 코드 실행 속도를 높일 수 있습니다.

버전 내역

R2015b에 개발됨

참고 항목

shortestpath | distances | nearest | graph | digraph