10. 그래프 알고리즘

<1> Dijkstra / 최단거리 개념

- 최단거리 개념

우리는 앞에서 BFS를 통해 최단거리를 계산할 수 있다는 것을 학습했습니다.

그러나 그래프에서 간선에 적혀있는 가중치가 전부 동일하지 않다면, 최단거리를 구하는 일은 생각보다 복잡해집니다.

위의 그림에서 S에서 E로 가는 최단거리는 실제 4입니다.

하지만 BFS를 이용하면 가장 가까이에 있는 노드부터 순차적으로 보게 되므로 바로 S와 바로 붙어있는 E의 최단거리를 100이라 판단하게 될 것입니다.

이런 문제를 해결하기 위해, 정말 다양한 알고리즘이 나오게 되었습니다.

우리는 그 다양한 알고리즘 중 두 가지를 학습할 것입니다.