알고리즘 7장
그래프 탐색: BFS 최단 거리
무가중치 그래프에서는 BFS 최초 방문 시점의 레벨이 시작점으로부터의 최소 간선 수입니다.
상태 변화
거리 확정
1
dist 0
2
3
dist 1
4
5
dist 2
1
0
2
1
3
1
4
2
5
2
불변식
점검
dist[start]=0
시작 정점의 거리를 0으로 둡니다.
첫 방문 확정
처음 방문한 정점의 거리가 최단 거리입니다.
다음 레벨
현재 거리 + 1로 인접 정점 거리를 채웁니다.
최단 거리 조건
간선 가중치가 있으면 Dijkstra나 다른 알고리즘이 필요합니다.