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

그래프 G = ( V , E ) 에서 두 개의 정점 uv 에 대해 u 에서 v 까지의 간단한 경로 가 하나만 있으면 유향 그래프는 단일 경로라고 합니다.

u

v

G=(V,E)

u

v

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

G

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

O(|V|)

s

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

u

v


답변

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

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

s

s

n(n−1)/2

n

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

s

u

t

s

t

결과를 배열에 저장하고 에서 | 전자 | (1)(S) = 0 . 어레이의 각 요소를 저장 노드로의 경로에있는 이전 노드의 인덱스 (예를 들어 사용 1 에서 연결할 수없는 노드 특수 마커로서 S ). 에서 경로 t가 될 것이다 ( S = R [ R [ t ] ] , , R [ R [ t

0

|E|−1

s=0

−1

s

s

t

.

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

그래프 트래버스

초기화 모두에게 1 .

R

−1

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

s

u

R[u]

사이클이 있으므로 노드에 두 번 이상 도달 할 수 있습니다. 데 것을 나타낸다 U가 이미 방문한되었다.

R[u]≠−1

u

정확성 증명

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

복잡성 증명

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

O(|V|)

Θ(|E0|)

V0

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

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

m

a

a

bi

∀i,a⇆bi

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

#V(G)

G

#E(G)

#C(G)

G

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

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

#V(G)<n

G

n

G

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

(a1,…,am)

주기를 십시오. 는 노드에 마이너스 의 노드 와 노드 있고 의 모서리가 와 관련되지 않은 의 모서리 와 때마다 및 있을 때마다 . 모든 경로 에서 경로 유도 경로를 포함하는 경우 ( 다음으로 이것을 대체 G

G′

G

{a1,…,am}

a

G

ai

a→G′b

∃i,ai→Gb

b→G′a

∃i,b→Gai

G′

G

b→a→c

b→ai→ai+1→…→aj→c

in ). 따라서 는 단일 경로입니다. 또한 사이클은 에지를 공유하지 않으므로 는 우리가 제거한 사이클을 제외하고 모든 사이클을 갖습니다 : . 유도에 의해 . 이후 , 우리가 .

G

G′

G

G′

G

#C(G′)=#C(G)−1

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

#V(G′)=#V(G)−m+1

#C(G)=#C(G′)+1≤#V(G)−m=n−m≤n−1

2|V|−2

답변