[WEEK03] DAY23 & Dijkstra

https://velog.io/@yerimii11/WEEK03-DAY23-Dijkstra 2021년 11월 25일에 작성된 게시글 아카이브입니다.  (사유: 블로그이전)

[WEEK03] DAY23 & Dijkstra

---

사진이 많으니 로딩을 기다려주세욥 ~!!

---

다익스트라 알고리즘

• 최단경로(최솟값)를 찾는 알고리즘

---

1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2
를 입력 받는다 (예시)

색은 상관없다.ㅋㅋ
빨리 그리겠다고 동기랑 같이 그려서 그럼 ㅋㅋㅋㅋ

---

부모노드가 0개인 1을 가장 먼저 탐색하는 것으로 작성된 리스트이다
최솟값을 0, inf, inf, inf... 로 초기셋팅한 후 cost를 갱신해준다

1번이 가리키는 노드는 2, 3, 4이고
1번을 pop한 후 탐색하는 과정에서 연결된 간선이 끊어지고
2, 3, 4번 노드만 남게 된다
최소힙을 사용해 거리가 1로 가장 짧은 4번 노드를 최소힙의 루트노드로 올려준다

마찬가지로 이번 루트노트인 4번노드도 pop 한 후 탐색을 시작한다
이 과정에서 4번과 연결되어있던 2, 3번 노드 간선이 끊어진다
4번 노드를 탐색하면서 최소 거리를 갱신해준다

---

여기서 4번노드를 기준으로 탐색하니 경로에 4번을 거치는 거리를 세면 된다
1->3 직진 경로는 거리가 5였지만
1->4->3 경로로 가는 거리는 1+3=4 이므로 기존의 5보다 더 작은 4로 리스트를 갱신해준다

마찬가지로 1에서 5로 가는 경로도 더 작은 수로 갱신해준다
1->5 로 바로 가는 루트는 처음에 없어서 무한대로 표시되어있었지만
4번노드를 거치면 1->4->5 순서로 가면 되므로 거리1+1=2을 갱신해준다
이 과정에서 5번노드가 append되어 최소힙에 추가된다

쭉 이어서 같은 방법으로 2번노드를 탐색하고 갱신하고 이 과정을 반복한다

5번을 탐색하기 위해 pop된 모습

---

---

3, 6번이 남았다(최소힙-cost가 낮은 노드가 루트)

3번에서는 2, 6번으로 가는 최솟값을 구해 갱신할 수 있다
하지만 이미 저장되있는 값이 8, 8보다 더 최솟값이라 새로 갱신은 안함

6은 갈 곳이 없기 때문에 여기서 끝.

---

코드로 작성하기

---

 

끝 !