계량 된 단일 경로 그래프에서 최단 경로 찾기 합니다.유uuVvvG = (

그래프 에서 두 개의 정점 와 에 대해 에서 까지의 간단한 경로 가 하나만 있으면 유향 그래프는 단일 경로라고 합니다. $u$

$v$

$G = (V, E)$

G=(V,E)

$u$

$v$

각 모서리에 양 또는 음의 가중치가 있지만 음의 가중치 사이클이 포함되지 않도록 unipathic graph 있다고 가정 합니다. $G$

이로부터 나는 찾으려 알고리즘이 소스 노드에서 모든 노드 발견 모든 최단 경로 . $O (| V |)$

O(|V|)

$s$

이 문제에 어떻게 접근 할 지 잘 모르겠습니다. 나는 그것이 음의 가중치 사이클을 포함하지 않는다는 사실을 사용하려고 노력하고 있습니다. 물론 노드 에서 사이의 최대 하나의 간단한 경로 입니다. $u$

$v$

답변

데이터 표현을 선택하십시오

먼저 결과의 크기를보십시오. 에서 다른 모든 노드 까지 최단 경로를 수집하려고 합니다. 경로의 평균 길이가 아닌 상수 (에 의해 제한되지 않는 한 : 어떤 목록 unipath, 그리고 당신이 뿌리를 내릴 경우에 대한 경로의 총 길이는 여기서 입니다 목록의 길이)에 따라 데이터 표현에주의해야합니다. 경로를 포함하는 구조는 경로간에 공유를 사용해야합니다. $s$

$s$

$n (n - 1) / 2$

n(n−1)/2

$n$

사이클을 제외하고 에서 다른 노드 까지 단일 경로가 있습니다 . 해당 경로가 중간 노드 통과하는 경우 경로 의 첫 번째 세그먼트는 에서 까지 원하는 경로입니다 . $s$
s
$u$
u
$t$
t
$s$
s
$t$
t

결과를 배열에 저장하고 에서 과 . 어레이의 각 요소를 저장 노드로의 경로에있는 이전 노드의 인덱스 (예를 들어 사용 에서 연결할 수없는 노드 특수 마커로서 ). 에서 경로 에 될 것이다 $0$

$| E | - 1$

|E|−1

$s = 0$

s=0

$- 1$

−1

$s$

$t$

. $(s = R [\dots R [t] \dots], \dots, R [R [t]], R [t], t)$

(s=R[…R[t]…],…,R[R[t]],R[t],t)

그래프 트래버스

초기화 모두에게 . $R$

$- 1$

−1

에서 시작하여 그래프의 깊이 우선 또는 너비 우선 순회를 수행합니다 . 노드 에 도달 할 때마다 를 이전 노드로 설정하십시오 . $s$

$u$

$R [u]$

R[u]

사이클이 있으므로 노드에 두 번 이상 도달 할 수 있습니다. 데 것을 나타낸다 이미 방문한되었다. $R [u] \neq - 1$

R[u]≠−1

$u$

정확성 증명

unipathic 특성으로 인해주기를 완료하지 않은 경우 각 노드에 도달하는 방법은 중요하지 않습니다. 간단한 경로는 하나뿐입니다.

복잡성 증명

알고리즘이 각 노드에 두 번 이상 도달 할 수 있으므로 복잡도가 인지 확실하지 않습니다 . 실제로 수행 된 작업은 이며 여기서 은 소스에서 도달 할 수있는 모서리입니다. 보다 정확하게, 우리는 한 상황에서만 두 번 이상 노드에 도달합니다. 노드가 특정 사이클에서 가장 먼저 도달하면이 경우 두 번 도달합니다 (간단한 경로에서 한 번, 사이클 완료 후 한 번) ). $O (| V |)$

O(|V|)

$Θ (| E_{0} |)$

Θ(|E0|)

$V_{0}$

그럼 unipathic graph에서 elementary cycle의 수는 노드 수에 따라 선형 적으로 증가한다는 것을 증명해 봅시다. (초등 사이클은 더 짧은 사이클을 포함하지 않는 사이클입니다.) 다음 논의에서는 그래프에 자체 에지가 없다고 가정합니다 (노드에서 자체 에지가 없음). 이러한 에지는 경로 구성과 관련이 없습니다. ).

단일 경로 그래프에는주기가있을 수 있지만 매우 제한적입니다. 우리가 어떻게 든 각 사이클을 별개의 노드 (또는 적어도 노드 당 제한된 수의 사이클)에 연결할 수 있다면 좋을 것입니다. 사이클이 노드를 공유 할 수 있습니까? 불행히도, 그렇습니다.

$m$
m
$a$
a
$a$
a
$b_{i}$
bi
$\forall i, a ⇆ b_{i}$
∀i,a⇆bi

그래서 우리는 더 열심히 일해야합니다. 자, 그것을 유도 적으로 증명하려고 노력합시다. 그래프 의 노드 수 , 가장자리 수, 자체 가장자리가 아닌 기본주기 수라고 합시다 . 가 단일 경로이고 비어 있지 않으면 이라고 주장합니다 . $# V (G)$

#V(G)

$G$

$# E (G)$

#E(G)

$# C (G)$

#C(G)

$G$

$# C (G) \leq # V (G) - 1$

#C(G)≤#V(G)−1

하나 또는 두 개의 노드가있는 그래프의 경우 이는 분명합니다. 어설 션이 모든 그래프에 대해 을 유지하고 가 노드를 갖는 단일 경로 그래프 라고 가정 합니다. 에 사이클이없는 경우 이면 케이스가 닫힙니다. 그렇지 않으면 기본 주기로 설정하십시오. $# V (G) < n$

#V(G)<n

$G$

$n$

$G$

$0 = # C (G) < # V (G)$

0=#C(G)<#V(G)

$(a_{1}, \dots, a_{m})$

(a1,…,am)

주기를 십시오. 는 노드에 마이너스 의 노드 와 노드 있고 의 모서리가 와 관련되지 않은 의 모서리 와 때마다 및 있을 때마다 . 모든 경로 에서 경로 유도 경로를 포함하는 경우 ( 다음으로 이것을 대체 $G^{'}$
G′
$G$
G
${a_{1}, \dots, a_{m}}$
{a1,…,am}
$a$
a
$G$
G
$a_{i}$
ai
$a \to_{G^{'}} b$
a→G′b
$\exists i, a_{i} \to_{G} b$
∃i,ai→Gb
$b \to_{G^{'}} a$
b→G′a
$\exists i, b \to_{G} a_{i}$
∃i,b→Gai
$G^{'}$
G′
$G$
G
$b \to a \to c$
b→a→c
$b \to a_{i} \to a_{i + 1} \to \dots \to a_{j} \to c$
b→ai→ai+1→…→aj→c
in ). 따라서 는 단일 경로입니다. 또한 사이클은 에지를 공유하지 않으므로 는 우리가 제거한 사이클을 제외하고 모든 사이클을 갖습니다 : . 유도에 의해 . 이후 , 우리가 . $G$
G
$G^{'}$
G′
$G$
G
$G^{'}$
G′
$G$
G
$# C (G^{'}) = # C (G) - 1$
#C(G′)=#C(G)−1
$# C (G^{'}) \leq # V (G^{'}) - 1$
#C(G′)≤#V(G′)−1
$# V (G^{'}) = # V (G) - m + 1$
#V(G′)=#V(G)−m+1
$# C (G) = # C (G^{'}) + 1 \leq # V (G) - m = n - m \leq n - 1$
#C(G)=#C(G′)+1≤#V(G)−m=n−m≤n−1

$2 | V | - 2$

2|V|−2

How IT

언제든지 물어보세요.

계량 된 단일 경로 그래프에서 최단 경로 찾기 합니다.유uuVvvG = (

답변

데이터 표현을 선택하십시오

그래프 트래버스

정확성 증명

복잡성 증명

답변