O(n*|V|^2) 미만의 솔루션이있을 것 같지 않으므로 여기서는 파이썬에서 너무 끔찍한 방법이 있습니다.
# some basic topologies
def lineE(N):
return(set((i,i+1) for i in range(N-1)))
def ringE(N):
return(lineE(N).union([(0,N-1)]))
def fullE(N):
return(set([(i,j) for i in range(N) for j in range(i)]))
# propagate visitors from x to y
def propagate(V, curr, x, y, d):
nexty = set()
for cx in curr[x]:
if not cx in V[y]["seen"]:
V[y]["seen"].add(cx)
V[y]["foaf"][d] = V[y]["foaf"].get(d,0) + 1
nexty.add(cx)
return(nexty)
# run for D iterations
def mingle(N, E, D):
V = dict((i, {"seen":set([i]), "foaf":{0:1}}) for i in range(N))
curr = dict((i, set([i])) for i in range(N))
for d in range(1, min(D+1, N)):
next = dict((i, set()) for i in range(N))
for (h, t) in E:
next[t] = next[t].union(propagate(V, curr, h, t, d))
next[h] = next[h].union(propagate(V, curr, t, h, d))
curr = next
return(V)
것은, 10 개 노드와 거리 3 그것을 밖으로 시도
N=10
D=3
for (topology, E) in [("line", lineE(N)), ("ring", ringE(N)), ("full", fullE(N))]:
V = mingle(N, E, D)
print "\n", topology
for v in V:
print v, V[v]["foaf"]
우리는 올바른 것
line
0 {0: 1, 1: 1, 2: 1, 3: 1}
1 {0: 1, 1: 2, 2: 1, 3: 1}
2 {0: 1, 1: 2, 2: 2, 3: 1}
3 {0: 1, 1: 2, 2: 2, 3: 2}
4 {0: 1, 1: 2, 2: 2, 3: 2}
5 {0: 1, 1: 2, 2: 2, 3: 2}
6 {0: 1, 1: 2, 2: 2, 3: 2}
7 {0: 1, 1: 2, 2: 2, 3: 1}
8 {0: 1, 1: 2, 2: 1, 3: 1}
9 {0: 1, 1: 1, 2: 1, 3: 1}
ring
0 {0: 1, 1: 2, 2: 2, 3: 2}
1 {0: 1, 1: 2, 2: 2, 3: 2}
2 {0: 1, 1: 2, 2: 2, 3: 2}
3 {0: 1, 1: 2, 2: 2, 3: 2}
4 {0: 1, 1: 2, 2: 2, 3: 2}
5 {0: 1, 1: 2, 2: 2, 3: 2}
6 {0: 1, 1: 2, 2: 2, 3: 2}
7 {0: 1, 1: 2, 2: 2, 3: 2}
8 {0: 1, 1: 2, 2: 2, 3: 2}
9 {0: 1, 1: 2, 2: 2, 3: 2}
full
0 {0: 1, 1: 9}
1 {0: 1, 1: 9}
2 {0: 1, 1: 9}
3 {0: 1, 1: 9}
4 {0: 1, 1: 9}
5 {0: 1, 1: 9}
6 {0: 1, 1: 9}
7 {0: 1, 1: 9}
8 {0: 1, 1: 9}
9 {0: 1, 1: 9}
를 얻을. 또한 100000 노드의 거리 100에 대한 간단한 토폴로지 실행은 노트북에서 약 1 분 정도 소요됩니다. 물론 밀도가 높은 그래프 (예 : fullE)가 있으면이 그래프가 폭발합니다.
N=100000
D=100
for (topology, E) in [("line", lineE(N)), ("ring", ringE(N))]:
V = mingle(N, E, D)
에서 [모든 최단 경로 문제 (http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm)는 거리 계산에 의해 그룹화 한 후 무엇을 추구 기본적으로, 당신은 아마 수 O (| V |^3)보다 훨씬 훌륭합니다. – Nuclearman
내 우선 순위 검색은 O (| E |)이며, 이는 내 경우에 O (| V |)와 같습니다. 모든 노드에서이 작업을 수행해야하므로 현재의 복잡성은 O (| V | ²)입니다. 지금 병렬 처리를 사용하여 프로세스 속도를 높이고 있지만 다른 제안 사항을 환영합니다! –
여전히 최악의 경우 O (| V |^3) 인 O (| V | * | E |) 여야합니다. 그러나, | V | | E |에 가까우면, 최단 경로를 나열해야하는 O (| V |^2) 개의 가능한 정점 조합이 있다는 것을 고려하면 할 수있는 것보다 많지는 않습니다. 비록 대부분의 정점이 차수가 2 이하일 경우, 가장 긴 경로 (또는 충분히 긴 경로)를 간단하게 나열하고 이들 중에서 가장 짧은 경로를 추출하는 것이 현실적 일 수 있습니다. – Nuclearman