그래프 최단경로 알고리즘 비교 & 대표문제

표로 정리

	Single Source Shortest Path (SSSP)	All-Pairs Shortest Paths (APSP)
Edge에 weight 없음	Breadth First Search (BFS)	Floyd-Warshall Algorithm
weight 있고, 음수 weight 없음	Dijkstra Algorithm	Floyd-Warshall Algorithm
weight 있고, 음수 weight 있음	Bellman-Ford Algorithm	Floyd-Warshall Algorithm

출처: https://shnoh.tistory.com/15

각각의 시간복잡도

V: vertex(정점) 수
E: Edge(간선) 수

• Breadth First Search (BFS)
  • $O(V+E)$ (인접리스트로 구현했을 때)
  • $O(V^2)$ (인접행렬로 구현했을 때)
• Dijkstra Algorithm(Greedy기반)
  • $O((V+E)*logV)$ (우선순위큐 이용했을 때)
    => $O(E*logV)$ (모든 정점이 출발지에서 도달 가능하다면)
  • $O(V^2)$ (우선순위큐 이용 안 했을 때)
• Bellman-Ford Algorithm
  • $O(V*E)$
• Floyd-Warshall Algorithm(DP기반)
  • $O(V^3)$

관련 문제

(추가중)

• Floyd-Warshall Algorithm
  • 프로그래머스 합승 택시 요금(2021 KAKAO) (V<=200)