distances

모든 노드 쌍의 최단 경로 거리

구문

d = distances(G)

d = distances(G,s)

d = distances(G,s,t)

d = distances(___,'Method',algorithm)

설명

d = distances(G)는 행렬 d를 반환합니다. 여기서 d(i,j)는 노드 i와 노드 j 사이의 최단 경로 길이입니다. 그래프가 가중 그래프(즉, G.Edges가 변수 Weight를 포함함)인 경우에는 가중치가 그래프에서 간선의 거리로 사용됩니다. 가중 그래프가 아닌 경우에는 모든 간선 거리가 1로 처리됩니다.

d = distances(G,s)는 소스 노드를 s로 정의된 노드로 제한하며, d(i,j)는 노드 s(i)에서 노드 j까지의 거리입니다.

d = distances(G,s,t)는 타깃 노드를 t로 정의된 노드로 추가적으로 제한하며, d(i,j)는 노드 s(i)에서 노드 t(j)까지의 거리입니다.

d = distances(___,'Method',algorithm)은 위에 열거된 구문에 나와 있는 입력 인수와 함께, 최단 경로를 계산하는 데 사용할 알고리즘을 선택적으로 지정합니다. 예를 들어, G가 가중 그래프(Weighted Graph)이면 distances(G,'Method','unweighted')는 G의 간선 가중치를 무시하고, 그 대신 모든 간선 가중치를 1로 처리합니다.

예제

모든 노드 쌍에 대한 최단 경로 거리

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

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

그래프에 포함된 모든 노드 쌍 사이의 최단 경로 거리를 계산합니다. 그래프 간선에 가중치가 없으므로 모든 간선 거리가 1로 처리됩니다.

d = distances(G)

d = 10×10

     0     1     1     1     2     3     3     3     4     5
     1     0     2     2     1     2     2     2     3     4
     1     2     0     2     3     4     4     4     5     6
     1     2     2     0     3     4     4     4     5     6
     2     1     3     3     0     1     1     1     2     3
     3     2     4     4     1     0     2     2     3     4
     3     2     4     4     1     2     0     2     3     4
     3     2     4     4     1     2     2     0     1     2
     4     3     5     5     2     3     3     1     0     1
     5     4     6     6     3     4     4     2     1     0

G가 무방향 그래프이므로 d는 대칭 행렬입니다. 일반적으로, d(i,j)는 노드 i와 노드 j 사이의 최단 경로 길이이며, 무방향 그래프의 경우 d(j,i)와 동일합니다.

예를 들어, 노드 1과 노드 10 사이의 최단 경로 길이를 구할 수 있습니다.

d(1,10)

ans = 5

지정된 소스에서의 최단 경로 거리

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

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

노드 1, 노드 2, 노드 3에서 그래프에 포함된 모든 다른 노드까지의 최단 경로 거리를 구합니다.

d = distances(G,[1 2 3])

d = 3×7

     0     1     1     1     1     2     2
     1     0     1     2     2     1     2
     1     1     0     2     2     1     2

d를 사용하여 노드 1에서 노드 7까지의 최단 경로 거리를 구합니다.

d(1,7)

ans = 2

지정된 타깃까지의 최단 경로 거리

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

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

노드 5와 노드 7에서 노드 2와 노드 3까지의 최단 경로 거리를 구합니다.

sources = [5 7];
targets = [2 3];
d = distances(G,sources,targets)

d = 2×2

     3     1
     4     2

d를 사용하여 노드 7과 노드 3 사이의 최단 경로 거리를 구합니다. 이 경우, d(i,j)는 노드 sources(i)에서 노드 targets(j)까지의 거리입니다.

d(2,2)

ans = 2

간선 가중치 무시하기

가중치 간선이 있는 유방향 그래프를 생성하고 플로팅합니다.

s = [1 1 1 2 5 3 6 4 7 8 8 8];
t = [2 3 4 5 3 6 4 7 2 6 7 5];
weights = [100 10 10 10 10 20 10 30 50 10 70 10];
G = digraph(s,t,weights);
plot(G,'EdgeLabel',G.Edges.Weight)

모든 그래프 노드 쌍 사이의 최단 경로 거리를 구합니다.

d = distances(G)

d = 8×8

     0    90    10    10   100    30    40   Inf
   Inf     0    20    50    10    40    80   Inf
   Inf   110     0    30   120    20    60   Inf
   Inf    80   100     0    90   120    30   Inf
   Inf   120    10    40     0    30    70   Inf
   Inf    90   110    10   100     0    40   Inf
   Inf    50    70   100    60    90     0   Inf
   Inf   100    20    20    10    10    50     0

G가 유방향 그래프이므로 d는 대칭 행렬이 아니며 d(i,j)는 노드 i와 노드 j 사이의 거리에 해당합니다. d의 Inf 값은 도달할 수 없는 노드에 해당합니다. 예를 들어, 노드 1에는 선행 노드가 없으므로 그래프의 다른 노드에서 노드 1에 도달할 수 없습니다. 따라서 d의 첫 번째 열에는 노드 1이 도달할 수 없는 노드임을 나타내는 많은 Inf 값이 포함되어 있습니다.

기본적으로, distances는 간선 가중치를 사용하여 거리를 계산합니다. 간선 가중치를 무시하고 모든 간선 거리를 1로 처리하기 위해서는 'Method'를 'unweighted'로 지정해야 합니다.

d1 = distances(G,'Method','unweighted')

d1 = 8×8

     0     1     1     1     2     2     2   Inf
   Inf     0     2     4     1     3     5   Inf
   Inf     4     0     2     5     1     3   Inf
   Inf     2     4     0     3     5     1   Inf
   Inf     5     1     3     0     2     4   Inf
   Inf     3     5     1     4     0     2   Inf
   Inf     1     3     5     2     4     0   Inf
   Inf     2     2     2     1     1     1     0

입력 인수

G — 입력 그래프

graph 객체 | digraph 객체

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

예: G = graph(1,2)

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

s — 소스 노드

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

소스 노드로, 하나 이상의 노드 인덱스 또는 노드 이름으로 지정되거나 'all'로 지정되어 모든 노드를 선택합니다.

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

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

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

예: distances(G,[1 2])

예: distances(G,'all',[1 3 5])

t — 타깃 노드

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

타깃 노드로, 하나 이상의 노드 인덱스 또는 노드 이름으로 지정되거나 'all'로 지정되어 모든 타깃 노드를 선택합니다.

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

예: distances(G,[1 2])

예: distances(G,'all',[1 3 5])

algorithm — 최단 경로 알고리즘

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

최단 경로 알고리즘으로, 다음 표에 나와 있는 옵션 중 하나로 지정됩니다.

옵션	설명
'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'는 일부 간선 가중치에 음수 값을 사용할 수 있으므로 더 유연합니다.

참고

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

예: distances(G,s,t,'Method','unweighted')

출력 인수

d — 노드 쌍 사이의 최단 경로 거리

행렬

노드 쌍 사이의 최단 경로 거리로, 행렬로 반환됩니다. d의 크기는 (소스 노드 개수)×(타깃 노드 개수)입니다. Inf의 값은 존재하지 않는 경로를 나타냅니다.

팁

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

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

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

버전 내역

R2015b에 개발됨

참고 항목

shortestpathtree | shortestpath | nearest | graph | digraph

×

예제 열기

이 예제의 수정된 버전이 있습니다. 사용자가 편집한 내용을 반영하여 이 예제를 여시겠습니까?

아니요, 수정된 버전을 덮어씁니다. 예