다익스트라 알고리즘

A -> B 로 가는 경로를 구해야 할경우 너비 우선 탐색은 최단거리를 구하고 다익스트라 알고리즘은 최단 시간 경로를 구하는 것이다.

다익스트라의 단계

1. 가장 가깝거나/짧은 곳 즉 도달하는데 가장 적게 걸리는 정점을 찾는다
2. 이 정점의 이웃 정점에 대해 현재의 위치보다 더 적은 경로가 존재하는지 확인. 만약 존재한다면 결과 수정
3. 그래프 상의 모든 정점에 대해 이러한 일을 반복
4. 최종 경로를 계싼

용어 설명

가중치

• 그래프의 각 간선이 가지는 숫자

가중그래프

• 가중치를 가지는 그래프는 가중 그래프라고 한다.
• 최단 경로를 계산할때는 다익스트라 알고리즘을 사용한다.

균일 그래프

• 가중치가 없는 그래프는 균일 그래프 라고 한다.
• 최단 경로를 계산할 때는 너비 우선 탐색을 사용한다.

싸이클

• 그래프가 어떤 정점에서 출발해서 한 바퀴 돌아 같은 정점에서 끝나는것

방향/무방향 그래프
방향은 화살표로 표현해 주고 무방향은 실선으로 표현하는데 무방향은 서로를 향한다(싸이클이다)

예시

📄 코드 보기

요약

• 너비 우선 탐색은 가중치가 없는 균일 그래프에서 최단 경로를 계산하는 데 사용
• 다익스트라 알고리즘은 가중 그래프에서 최단 거리를 계산하는 데 사용
• 다익스트라 알고리즘은 모두 가중치가 양수일 때만 정상적으로 동작
• 만약 가중치가 음수이면 벨만-포드 알고리즘을 사용한다.