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)

Figure contains an axes object. The axes object contains an object of type graphplot.

그래프에 포함된 모든 노드 쌍 사이의 최단 경로 거리를 계산합니다. 그래프 간선에 가중치가 없으므로 모든 간선 거리가 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)

Figure contains an axes object. The axes object contains an object of type graphplot.

노드 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)

Figure contains an axes object. The axes object contains an object of type graphplot.

노드 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)

Figure contains an axes object. The axes object contains an object of type graphplot.

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

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

입력 인수

모두 축소

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

예: G = graph(1,2)

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

소스 노드로, 하나 이상의 노드 인덱스 또는 노드 이름으로 지정되거나 '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])

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

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

예: distances(G,[1 2])

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

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

옵션설명
'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의 크기는 (소스 노드 개수)×(타깃 노드 개수)입니다. Inf의 값은 존재하지 않는 경로를 나타냅니다.

팁

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

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

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

확장 기능

모두 확장

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

버전 내역

R2015b에 개발됨

참고 항목

| | | |