둘 다 단일 소스에서 최단 경로를 찾는 데 사용할 수 있습니다. BFS는에서 실행되고 O(E+V)Dijkstra는 O((V+E)*log(V)).
또한 Dijkstra가 라우팅 프로토콜에서와 같이 많이 사용하는 것을 보았습니다.
따라서 BFS가 똑같은 일을 더 빨리 할 수 있다면 왜 Dijkstra의 알고리즘을 사용합니까?
답변
Dijkstra는 각 단계에 대해 1이 아닌 거리를 할당 할 수 있습니다. 예를 들어, 라우팅에서 거리 (또는 가중치)는 속도, 비용, 선호도 등에 의해 할당 될 수 있습니다. 그런 다음 알고리즘은 소스에서 순회 그래프의 모든 노드까지의 최단 경로를 제공합니다.
한편 기본적으로 그냥 작은 발견의 효과가 일어나는 모든 반복에 (당신이 당신의 응용 프로그램에서 전화를 원하는 링크, 가장자리) 한 “단계”로 검색 확장 BFS 단계의 수를 그 어떤에 도착하는 데 걸리는은 소스 ( “루트”)에서 주어진 노드.
답변
여행 웹 사이트를 고려한다면 노드의 가중치 (거리) 때문에 Dijkstra의 알고리즘을 사용합니다.
모든 노드간에 동일한 거리를 고려한다면 BFS가 더 나은 선택입니다.
예를 들어, = 10, = 20, = = 5로 A -> (B, C) -> (F)주어진 간선 가중치를 고려하십시오 .A->BA->CB->FC->F
여기서 BFS를 적용하면 답은 ABF 또는 ACF가됩니다. 둘 다 최단 경로 (가장자리 수와 관련하여)이기 때문입니다. 그러나 Dijstra를 적용하면 답은 연결에 대한 가중치를 고려하기 때문에 ABF가됩니다. 통로.
답변
Dijkstra의 알고리즘
- 가중 그래프의 BFS와 같습니다.
- 모든 비용이 동일하면 Dijkstra = BFS
