-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
BFs
20.03.25 17:56 작성 조회수 328
0
그래프 상의 최단거리의 경우 전에 BFS문제를 사용했던 걸로 알고있습니다. 다익스트라도 최단거리 관련문제인데
다익스트라는 BFS의 한종류의 알고리즘으로 보면되나요?
BFS와 다익스트라의 차이점이 있다면 궁금합니다
답변을 작성해보세요.
0
김태원
지식공유자2020.03.25
최단거리를 BFS로 풀수도 있고, 다익스트라로 풀수도 있습니다. 다익스트라는 동적계획법에 가까운 알고리즘입니다.정점의 개수가 많아지면 다익스트라가 좀더 효율적입니다. 아무래도 BFS로 하다보면 queue 자료구조로 같은 정점이 여러번 입력되는 경우가 생기기 때문에 다익스트라에 비해 비효율적입니다. BFS로두 구현해보고 다익스트라로도 구현해보면 느낄 수 있을 겁니다.
답변 1