Main Content

이 페이지의 최신 내용은 아직 번역되지 않았습니다. 최신 내용은 영문으로 볼 수 있습니다.

shortestpath

두 개 단일 노드 사이의 최단 경로

설명

예제

P = shortestpath(G,s,t)는 소스 노드 s에서 시작하여 타깃 노드 t에서 끝나는 최단 경로를 계산합니다. 그래프가 가중 그래프(즉, G.Edges가 변수 Weight를 포함함)인 경우에는 가중치(Weight)가 그래프에서 간선의 거리로 사용됩니다. 가중 그래프가 아닌 경우에는 모든 간선 거리가 1로 처리됩니다.

예제

P = shortestpath(G,s,t,'Method',algorithm)은 최단 경로를 계산하는 데 사용할 알고리즘을 선택적으로 지정합니다. 예를 들어, G가 가중 그래프(Weighted Graph)이면 shortestpath(G,s,t,'Method','unweighted')G의 간선 가중치를 무시하고, 그 대신 모든 간선 가중치를 1로 처리합니다.

예제

[P,d] = shortestpath(___)는 위에 열거된 구문에 나와 있는 입력 인수와 함께, 최단 경로의 길이 d를 추가로 반환합니다.

예제

[P,d,edgepath] = shortestpath(___)s에서 t까지의 최단 경로에 있는 모든 간선의 간선 인덱스 edgepath를 추가로 반환합니다.

예제

모두 축소

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

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

Methodunweighted로 지정하여 간선 가중치를 무시합니다. 그러면 모든 간선이 가중치가 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)

입력 인수

모두 축소

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

예: G = graph(1,2)

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

소스 및 타깃 노드 ID로, 노드 인덱스 또는 노드 이름의 개별 인수로 지정됩니다.

예제
스칼라 노드 인덱스1
문자형 벡터 노드 이름'A'
string형 스칼라 노드 이름"A"

예: shortestpath(G,2,5)는 노드 2와 노드 5 사이의 최단 경로를 계산합니다.

예: shortestpath(G,'node1','node2')는 명명된 노드 node1node2 사이의 최단 경로를 계산합니다.

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

옵션설명
'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')

출력 인수

모두 축소

노드 사이의 최단 경로로, 노드 인덱스로 구성된 벡터 또는 노드 이름으로 구성된 배열로 반환됩니다. 노드 사이에 경로가 없는 경우 P는 비어 있습니다({}).

  • st가 숫자형 노드 인덱스를 포함하는 경우 P는 노드 인덱스로 구성된 숫자형 벡터입니다.

  • st가 노드 이름을 포함하면 P는 노드 이름으로 구성된 셀형 배열 또는 string형 배열입니다.

st 사이에 최단 경로가 여러 개 있는 경우 P는 이러한 경로 중 하나만 포함합니다. 반환되는 경로는 Method가 지정하는 알고리즘에 따라 바뀔 수 있습니다.

최단 경로 거리로, 숫자형 스칼라로 반환됩니다. dP에 있는 연속적인 노드 사이의 간선 가중치를 모두 합한 값입니다. 노드 사이에 경로가 없는 경우 dInf입니다.

최단 경로에 있는 간선으로, 간선 인덱스 벡터로 반환됩니다. 다중 그래프에서는 이 출력값이 두 노드 사이의 어느 간선이 최단 경로에 있는지 나타냅니다. 이 출력값은 highlight'Edges' 이름-값 쌍과 함께 사용할 수 있습니다(예: highlight(p,'Edges',edgepath)).

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

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

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

R2015b에 개발됨