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
가중 그래프(Weighted Graph)의 최단 경로
가중치 간선이 있는 그래프를 생성하고 플로팅합니다.
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)
그래프 노드 사이의 유클리드 거리를 계산하여 그래프에 간선 가중치를 추가합니다. 거리는 노드 좌표 에서 다음과 같이 계산됩니다.
와 를 계산하려면 먼저 findedges
를 사용하여 그래프에 있는 각 간선의 소스 노드와 타깃 노드를 기술하는 벡터 sn
과 tn
을 구합니다. 그런 다음 sn
과 tn
을 사용하여 x 및 y 좌표 벡터의 요소를 참조하고 와 를 계산합니다. hypot
함수는 제곱합의 제곱근을 계산하므로 와 를 입력 인수로 지정하여 각 간선의 길이를 계산합니다.
[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)
입력 인수
s,t
— 소스 및 타깃 노드 ID(개별 인수)
노드 인덱스 | 노드 이름
소스 및 타깃 노드 ID로, 노드 인덱스 또는 노드 이름의 개별 인수로 지정됩니다.
값 | 예제 |
---|---|
스칼라 노드 인덱스 | 1 |
문자형 벡터 노드 이름 | 'A' |
string형 스칼라 노드 이름 | "A" |
예: shortestpath(G,2,5)
는 노드 2와 노드 5 사이의 최단 경로를 계산합니다.
예: shortestpath(G,'node1','node2')
는 명명된 노드 node1
과 node2
사이의 최단 경로를 계산합니다.
algorithm
— 최단 경로 알고리즘
'auto'
(디폴트 값) | 'unweighted'
| 'positive'
| 'mixed'
| 'acyclic'
최단 경로 알고리즘으로, 다음 표에 나와 있는 옵션 중 하나로 지정됩니다.
옵션 | 설명 |
---|---|
'auto' (디폴트 값) |
|
'unweighted' | 모든 간선 가중치를 |
'positive' | 모든 간선 가중치가 음수가 아니어야 하는 데이크스트라 알고리즘(Dijkstra Algorithm)입니다. |
'mixed' (digraph 에만 해당) | 그래프에 음의 순환을 허용하지 않는 유방향 그래프에 대한 벨만-포드 알고리즘(Bellman-Ford Algorithm)입니다.
|
'acyclic' (digraph 에만 해당) | 가중치 간선이 있는 DAG(유방향 비순환 그래프)에 대한 성능을 향상시키도록 설계된 알고리즘입니다. 유방향 그래프가 비순환적(acyclic)인지 확인하려면 |
참고
대부분의 그래프에 대해 'unweighted'
알고리즘이 가장 빠르며, 그 다음이 'acyclic'
, 'positive'
, 'mixed'
순입니다.
예: shortestpath(G,s,t,'Method','acyclic')
출력 인수
P
— 노드 사이의 최단 경로
노드 인덱스 | 노드 이름
노드 사이의 최단 경로로, 노드 인덱스로 구성된 벡터 또는 노드 이름으로 구성된 배열로 반환됩니다. 노드 사이에 경로가 없는 경우 P
는 비어 있습니다({}
).
s
와t
가 숫자형 노드 인덱스를 포함하는 경우P
는 노드 인덱스로 구성된 숫자형 벡터입니다.s
와t
가 노드 이름을 포함하면P
는 노드 이름으로 구성된 셀형 배열 또는 string형 배열입니다.
s
와 t
사이에 최단 경로가 여러 개 있는 경우 P
는 이러한 경로 중 하나만 포함합니다. 반환되는 경로는 Method
가 지정하는 알고리즘에 따라 바뀔 수 있습니다.
d
— 최단 경로 거리
스칼라
최단 경로 거리로, 숫자형 스칼라로 반환됩니다. d
는 P
에 있는 연속적인 노드 사이의 간선 가중치를 모두 합한 값입니다. 노드 사이에 경로가 없는 경우 d
는 Inf
입니다.
edgepath
— 최단 경로에 있는 간선
간선 인덱스 벡터
최단 경로에 있는 간선으로, 간선 인덱스 벡터로 반환됩니다. 다중 그래프에서는 이 출력값이 두 노드 사이의 어느 간선이 최단 경로에 있는지 나타냅니다. 이 출력값은 highlight
의 'Edges'
이름-값 쌍과 함께 사용할 수 있습니다(예: highlight(p,'Edges',edgepath)
).
팁
shortestpath
,shortestpathtree
,distances
함수는 음의 간선 가중치를 갖는 무방향 그래프를 지원하지 않으며, 더 일반적으로는 음의 순환을 포함하는 모든 그래프를 지원하지 않습니다. 그 이유는 다음과 같습니다.음의 순환은 노드에서 다시 자기 자신으로 연결되는 경로이며, 경로의 간선 가중치의 합이 음수가 됩니다. 음의 순환이 두 노드 사이의 경로에 있는 경우, 음의 순환을 순회하여 항상 더 짧은 경로를 발견할 수 있으므로 두 노드 사이에 최단 경로가 존재하지 않습니다.
무방향 그래프에서 하나의 음의 간선 가중치는 하나의 음의 순환을 생성합니다.
확장 기능
C/C++ 코드 생성
MATLAB® Coder™를 사용하여 C 코드나 C++ 코드를 생성할 수 있습니다.
이름 값 인수는 상수여야 합니다.
'positive'
,'unweighted'
및'auto'
방법만 지원됩니다.지정된 노드 사이에 경로가 없는 경우 출력 인수
P
와edgepath
의 크기는0
×0
이 아니라1
×0
입니다.
스레드 기반 환경
MATLAB®의 backgroundPool
을 사용해 백그라운드에서 코드를 실행하거나 Parallel Computing Toolbox™의 ThreadPool
을 사용해 코드 실행 속도를 높일 수 있습니다.
버전 내역
R2015b에 개발됨
참고 항목
shortestpathtree
| distances
| nearest
| graph
| digraph
MATLAB 명령
다음 MATLAB 명령에 해당하는 링크를 클릭했습니다.
명령을 실행하려면 MATLAB 명령 창에 입력하십시오. 웹 브라우저는 MATLAB 명령을 지원하지 않습니다.
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)