이재호
다익스트라 알고리즘 본문
다익스트라 알고리즘은 최단시간경로를 구할때 사용합니다, 너비우선탐색은 최단경로를 구할때 사용합니다.
다익스트라 알고리즘 4단계
- 가장 가격이 싼 정점을 찾는다, 가장 가격이 싼 정점이란 도달하는데 시간이 가장 적게 걸리는 정점을 말한다
- 이 정점의 이웃정점들의 가격을 조사한다.
- 그래프상 모든 정점에 이러한 일을 반복한다.
- 최종 경로 계산
다 익스트라 알고리즘을 사용할떄, 그래프의 각 간선은 어떤 숫자를 가진다
이 숫자를 가중치라고 하며 가중치를 가지는 그래프를 가중그래프(다익스트라 알고리즘) , 가중 그래프가 없는 그래프를 균일 그래프라고 한다(너비우선탐색)
다 익스트라 알고리즘을 사용하면 최소화가 가능합니다.
다익스트라 알고리즘을 사용한 물물교환
라마라는 친구는 악보를 팔아서 피아노를 구하고 싶어합니다
알렉스라는 친구는 라마에게 악보를 팔면 자기가 좋아하는 밴드의 포스터를 준다고 합니다
그러나 5달러를 더 주면 희귀본 LP도 준다고 합니다
그런데 여기서 에이미라는 친구가 LP에 흥미를 느낍니다 그 LP에 돈을 더 보태면 자기의 기타나 드럼세트를 준다고 합니다
그런데 베토벤이 나타나서 그 기타나 드럼 둘중에 한개를 를 주면 피아노를 준다고 합니다
경제창조 입니다 악보 하나로 피아노를 살수 있는 경로가 생겼는데 주변에 좋은 친구들 정말 많이 둔거 같습니다 개부럽네요
이걸 그래프로 나타나면 이렇습니다
이 그래프를 이용해 각 정점에 대한 가격표를 만듭니다
| 정점 | 부모 |
| 포스터 | 0 |
| LP | 5 |
| 기타 | - 아직 정점에 도달하지 못함 |
| 드럼 | - 아직 정점에 도달하지 못함 |
| 피아노 | - 아직 정점에 도달하지 못함 |
알고리즘을 진행하면서 계속 표를 수정합니다
| 정점 | 부모 |
| 포스터 | 악보 |
| LP | 악보 |
| 기타 | - 아직 정점에 도달하지 못함 |
| 드럼 | - 아직 정점에 도달하지 못함 |
| 피아노 | - 아직 정점에 도달하지 못함 |
1단계 : 가장 가격이 싼 정점을 찾습니다. 이 경우 포스터가 0달러로 가장 쌉니다, 더 싼 가격에 살수 있는 다른 방법은 없습니다.
2단계 : 이웃까지 도달하는데 걸리는 시간을 계산합니다
| 부모 | 정점 | 가격 |
| 악보 | LP | 5 |
| 악보 | 포스터 | 0 |
| 포스터 | 기타 | 30 |
| 포스터 | - 아직 정점에 도달하지 못함 | 35 |
| 피아노 | - 아직 정점에 도달하지 못함 | - |
다시 1단계 : LP가 5달러로 두번째로 싼 정점입니다
다시 2단계 : 모든 이웃 정점의 가격을 갱신합니다
| 부모 | 정점 | 가격 |
| 악보 | LP | 5 |
| 악보 | 포스터 | 0 |
| LP | 기타 | 20 |
| LP | 드럼 | 25 |
| 피아노 | - 아직 정점에 도달하지 못함 | - |
드럼과 기타의 가격이 바뀌었습니다 LP랑 바꾸고 다른거랑 바꾸는게 더 ㄱㅇㄷ인 상황이 됐습니다.
그래서 이제 LP가 두 악기의 새로운 부모 정점이 됩니다
베이스 기타가 그 다음으로 싼 항목입니다, 그 이웃 정점도 갱신합니다.
| 부모 | 정점 | 가격 |
| 악보 | LP | 5 |
| 악보 | 포스터 | 0 |
| LP | 기타 | 20 |
| LP | 드럼 | 25 |
| 기타 | 피아노 | 40 |
이제 기타와 피아노를 바꾸면서 드디어 피아노의 가격을 알게 되었습니다 기타가 피아노의 정점입니다
그럼 드럼도 봐볼까용?
| 부모 | 정점 | 가격 |
| 악보 | LP | 5 |
| 악보 | 포스터 | 0 |
| LP | 기타 | 20 |
| LP | 드럼 | 25 |
| 드럼 | 피아노 | 35 |
holy shit 드럼이랑 피아노랑 바꾸는게 더 싼 가격으로 물물 교환을 할수 있습니다
그럼으로 라마가 가장 싸게 살수 있는 경로는
LP -> 드럼 -> 피아노 순서입니다 ㅊㅋㅊㅋ