BFS를 통해 전체 그래프를 반복하는 알고리즘이 있으며 모든 노드의 최소값을 찾기 위해 점수를 업데이트합니다. 그리고 이것의 런타임 복잡성은 O (V + E)라고 믿습니다. 이것은 Dijkstra보다 낫다고 생각합니다. 이 알고리즘이 옳다고 생각할만큼 순진하지는 않습니다. 그러나 어떤 경우에 최적의 최소 경로를 찾지 못할 지 궁금합니다. 여기에 내가 가지고있는 코드
from queue import Queue
ad_list = {
'A': {'B': 1, 'D': 3},
'B': {'A': 1, 'D': 1, 'C': 5},
'D': {'A': 3, 'B': 1, 'C': 3},
'C': {'B': 5, 'D': 3}
}
min_weights = {
'A': 0,
'B': float('inf'),
'C': float('inf'),
'D': float('inf'),
}
def fake_dijkstra(ad_list):
queue = Queue()
queue.put('A')
visited = {}
global min_weights
while not queue.empty():
key = queue.get()
# update score
children = ad_list[key]
for child_key, value in children.items():
if min_weights[child_key] > min_weights[key] + value:
min_weights[child_key] = min_weights[key] + value
if key in visited:
continue
visited[key] = True
children = ad_list[key]
for child_key, value in children.items():
queue.put(child_key)
fake_dijkstra(ad_list)
print(min_weights)
# for this case, it correctly finds the min weight to all nodes
{'A': 0, 'B': 1, 'C': 5, 'D': 2}
어떤 피드백이라도 대단히 감사하겠습니다. 나는 알고리즘을 좋아한다 :).
귀하의 알고리즘은 O (| V | + | E |) 가 아닙니다 .
각 노드가 다른 모든 노드와 연결된 완전 연결 그래프 G (V, E)를 고려하십시오 .
알고리즘에서 이러한 그래프의 각 노드를 대기열 | V-1 |에 추가합니다. 시간, 시작 노드가 대기열 | V |에 추가됩니다. 타임스. 따라서 큐에 있던 총 요소 수는 | V | x | V-1 | + 1
큐의 각 요소에 대해 모든 | V-1 |을 반복합니다. 최소 체중을 확인하는 어린이.
따라서 총 단계 수는 | V | x | V-1 | x | V-1 | 물론 O (| V | ³)
큐에 사용되는 데이터 구조에 따라 Dijkstra의 알고리즘 범위는 O (| V | ² + | E |) 에서 O (| V | x log | V | + | E |)까지 입니다. 완전히 연결된 그래프 | E | = | V | ² , 따라서 Dijkstras 알고리즘은 O (| V | ²)입니다.
따라서 알고리즘이 주어진 그래프에 대한 최단 경로를 찾을 수있는 것 같습니다 (100 % 확실하지는 않지만 카운터 예제를 찾을 수 없음). 그러나 노드의 자식을 여러 번 재평가하기 때문에 일반적인 BFS가 아닙니다. 그것은 또한 Dijkstra의 알고리즘과의 차이점입니다. 그 당시 노드 X의 자식이 평가되기 때문에 (즉, X-> Y에서 단계를 밟음) A에서 X까지 더 짧은 경로가 없음이 보장됩니다. 따라서 O- 복잡도 가 낮습니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다