shortestpathtree
노드의 최단 경로 트리
구문
설명
TR = shortestpathtree(___,Name,Value)shortestpathtree(G,s,'OutputForm','vector')는 최단 경로 트리를 설명하는 숫자형 벡터를 반환합니다.
예제
소스 노드를 기준으로 하여 그래프에서 도달 가능한 기타 노드 각각에 대한 최단 경로를 구하고 결과를 플로팅합니다.
유방향 그래프를 생성합니다.
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: [13×1 table]
Nodes: [8×0 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
입력 인수
이름-값 인수
출력 인수
팁
shortestpath,shortestpathtree,distances함수는 음의 간선 가중치를 갖는 무방향 그래프를 지원하지 않으며, 더 일반적으로는 음의 순환을 포함하는 모든 그래프를 지원하지 않습니다. 그 이유는 다음과 같습니다.음의 순환은 노드에서 다시 자기 자신으로 연결되는 경로이며, 경로의 간선 가중치의 합이 음수가 됩니다. 음의 순환이 두 노드 사이의 경로에 있는 경우, 음의 순환을 순회하여 항상 더 짧은 경로를 발견할 수 있으므로 두 노드 사이에 최단 경로가 존재하지 않습니다.
무방향 그래프에서 하나의 음의 간선 가중치는 하나의 음의 순환을 생성합니다.
확장 기능
버전 내역
R2015b에 개발됨
참고 항목
shortestpath | distances | nearest | graph | digraph
