hyeoneee's blog

알고리즘 시험에 패스한 기념으로

그동안 알고리즘 공부한걸 정리해보고자 한다 ^^ (기쁜맘으로)

그렇담 우선 Graph 최단거리 3종 아이들부터 정리해보고자 한다.

최단거리 알고리즘은 3가지가 대표적이다.

1. 다익스트라

2. 벨만포드

3. 플로이드 워셜

1) 시작점 , 도착점

1 to 1 : 다익스트라

1 to N : 다익스트라

N to 1 : 다익스트라 (역방향 그래프를 만들어 도착점을 출발점으로 하는 1 to N 다읷트라 수행) - 역다익

N to N : 플로이드 워셜

2) 간선의 가중치

가중치가 없으면?   BFS

가중치가 있으면서 양수이면 ? 다익스트라 (=> Priority Queue 사용)

가중치가 있으면서, 음수이면? 벨만포드 

3) 트리 

-> LCA