백준 최단경로 알고리즘

서론

단계별로 풀어보기: 최단 경로

이번에 최단경로 찾는 문제들을 많이 풀어보면서 공부한 알고리즘들을 정리해놓으려고 합니다.

정리

구분	BFS,DFS	Dijkstra	Bellman-Ford	Floyd-Warshall
가중치	X	O	O	O
		가중치가 양의 정수일 때만 가능하다.	가중치가 음의 정수일 때도 가능하다.	가중치가 음의 정수일 때도 가능하다. (단, 음의 사이클이 없어야 한다).
구현	que, stack 사용	heapq 사용	DP방식 distance[n] = min(distance[n], distance[m] + E(m, n))	DP방식 distance[i,j] = min(distance[i,j], distance[i,n] + distance[n,j]) 이차원 배열(행렬) 사용
시간 복잡도	O(V+E)	O(ElogV)	O(VE)	O(V^3)
사용 케이스	1:N	1:N	1:N	N:N

생각