1. BFS
가중치가 없는 경우 사용.
시작노드에서 최종노드까지 가는데 지나온 간선의 개수가 거리가 된다.
모든 노드를 검사하면서 인접한 노드를 검사하기 때문에
그래프를 인접 리스트로 나타내면
인접 행렬로 나타내면 가 된다.
따라서 그래프를 인접 리스트로 나타내자.
DFS는? BFS에 비해 비효율적이라 사용하지 않는다.
2. 다익스트라
가중치가 있는 경우 사용. 특히 가중치가 서로 다를 때.
이동한 간선의 개수가 적다고 최단거리가 아닌 경우이다.
이럴 때는 BFS를 사용해 구할 수 없다.
※ 가중치에 음수가 있으면 사용할 수 없다. (벨만-포드!)
우선순위 큐를 이용해 가중치가 짧은 간선을 선택한다.
과정)
0. 각 노드까지의 최단거리를 저장할 리스트를 만든다.(최소값으로 갱신하므로 방문하지 않은 노드는 무한으로 초기화)
1. 시작노드 설정
2. 시작노드 기준 인접한 노드의 최소비용을 저장
3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드 선택
4. 선택한 노드에서 방문하지 않은 노드로 가는 최소비용 저장
5. 반복
'알고리즘' 카테고리의 다른 글
| [백준 알고리즘] 2251번 물통. 파이썬(python)/ dfs, bfs (0) | 2022.10.19 |
|---|---|
| 소수구하기. 에라토스테네스의 체 (0) | 2022.09.26 |
| a부터 b까지의 합 (0) | 2022.07.25 |
| 최대공약수, 최소공배수 (0) | 2022.07.25 |
| [백준 알고리즘] 2468번 안전 영역. 파이썬(python) (0) | 2022.07.20 |