최단 거리 알고리즘이란 그래프 상 노드 간의 비용을 최소화 하는 알고리즘이다. 다익스트라 알고리즘, 플로이드 워셜 , 벨만 포드 등이 있다.
다익스트라는 그리디와 동적 계획법이 합쳐진 경우다.
이 그림을 예시로 들어보겠다.
다익스트라의 테이블에서 초기 상태엔 직접적으로 바로 가는게 없다면 inf (무한대)를 넣고, (1,1)과 같이 자기 자신에게 향하는 비용은 0으로 표기한다.
그 다음 시작 노드를 선정한다. 1을 선정하면, 노드 1을 방문했다고 처리한다. 1 기준에서 최단인 노드 2를 그 다음에 방문한다. 노드 2 기준에서 다시 보면, 노드 3이 제일 가깝기 때문에 노드 3에 방문한다. 이때, 노드 1은 노드 3까지 갈 수 있다는 정보를 알게 되어, 비용 값을 0 3 5 8 9 로 업데이트한다. (inf → 5)
그 다음 짧은 4번 노드를 방문한다. 이제 1에서 4까지 가는걸 노드 2와 3을 거쳐 가는게 더 빠른걸 깨달아서 또 업데이트한다. 5로 못가니 여기서 업데이트가 끝난다. 이러면 노드 1에 대해 각 노드 별 최단 거리는 0 3 5 6 9 가 된다. 실제 네트워크에서 많이 사용하는 방식이다.
모든 노드에 대해 모든 최단 거리를 구하자면 다음과 같은 타임 스탭을 밟는다.
초기화 : 시작 정점을 선택하고, 시작 정점으로 부터 나머지 정점간의 최단거리를 저장한다. 그냥 시작 정점으로부터의 거리인데 인접해 있지 않으면, 무한대로 설정한다.아직 처리하지 않은 정점중에 최단 거리가 가장 짧은 정점을 선택한다. 선택한 정점을 기준으로 인접한 정점간의 최단거리를 갱신한다. 선택된 정점을 통해 인접한 정점까지의 거리와 기존에 저장된 최단 거리를 비교해 갱신한다. 모든 정점이 처리될 때까지 반복한다.
이런 상황에서, A가 처음 노드고, 그 이후에 B로 갔다고 햇을 때, A에서 B로 가는 최단 경로는 5로 확정이 되었다. 하지만 만약 x가 -5보다 더 작다면, 아닐 수도 있다. 이와 같이 음수라면, 최단임을 확정지을 수 없어서 문제가 생긴다.
#Step 1 : 시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트 시키고, 시작노드를 방문한 노드로 체크한다.
Dist 배열은 각 노드까지 가는데 최소 비용
visited는 갔던 곳을 표시하기 위해(한번 갔으면 이제 안감)