강의

멘토링

커뮤니티

인프런 커뮤니티 질문&답변

dev.kkim님의 프로필 이미지
dev.kkim

작성한 질문수

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

12. 플로이드-와샬(그래프 최단거리)

플로이드 워샬과 다익스트라

작성

·

188

0

안녕하세요 선생님, 플로이드 워샬 알고리즘을 공부하다 궁금한 점이 있어 질문드립니다. 

플로이드 워샬은 모든 정점에서 모든 정점으로의 최단거리를 의미하고 다익스트라는 한 정점에서 나머지 정점으로 갈 때의 최단거리를 구하는것으로 알고있는데 그럼 다익스트라는 플로이드 워샬의 포함되는 알고리즘인지 궁금합니다. 또한 모든 다익스트라 문제가 플로이드 워샬로 풀리는지도 궁금합니다.

답변 1

1

김태원님의 프로필 이미지
김태원
지식공유자

안녕하세요. 둘의 포함관계라기 보다는 각자 독립적인 알고리즘이라고 봐야 합니다.

그리고 다익스트라 문제가 플로이드 워샬로 풀리기야 하겠지만 굳이 시간복잡도가 나쁜 플로이드-워샬로 풀 이유가 없습니다. 

dev.kkim님의 프로필 이미지
dev.kkim

작성한 질문수

질문하기