
🌟 다익스트라 알고리즘이란?하나의 시작 정점에서 다르정점까지의 최단 경로를 계산하는 것이다. 최단 경로 알고리즘이라고도 불린다! ⚒️ Dijkstra의 최단 경로 알고리즘다음과 같은 그림에서 최단경로를 계산하려고 한다. 각 단계에서 S안에 있지 않은 정점 중에서 가장 distance값이 작은 정점을 S에 추가한다.정점 W를 거쳐서 정점 u로 가는 가상적인 더 짧은 경로가 있다고 가정해보자! 그러면 정점 v에서 정점 u까지의 거리는 v->w->u (경로2 + 경로3) 거리가 된다.그러나 경로 2는 경로 1보다 항상 길 수 밖에 없다. 현재 distance 값이 가장 작은 정점은 u이기 때문이다. => 거리1 이 알고리즘을 해결하기 위해선 3가지를 고려해야한다. directionvisitedqueued..