Dijkstra2 BOJ 1753 최단경로 BOJ 1753 최단경로[https://www.acmicpc.net/problem/1753] 다익스트라를 적용할 수 있는 기본문제입니다. 아래 주소에 다익스트라에 관한 설명과 본 문제의 테스트케이스를 이용한 예제를 확인할 수 있습니다.[http://sycho-lego.tistory.com/7] 우선순위 큐를 이용하여 다익스트라를 구현하였습니다. 정답코드는 아래 주소에서 확인할 수 있습니다.[https://github.com/choseungyoon/Algorithm/blob/master/BOJ/1753_%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C.cpp] 2017. 10. 6. 다익스트라 알고리즘(Dijkstra) 다익스트라 알고리즘(Dijkstra Algorithm) 그래프 내에서 최단경로를 정하는 알고리즘은 여러가지가 있습니다. 그 중 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구할 때 사용됩니다.또한 모든 간선의 가중치가 양의 가중치를 가지고 있을 때 사용할 수 있습니다. 다익스트라의 기본적인 원리는 한 정점에서 갈 수 있는 다른 정점 중, 작은 가중치 간선을 우선적으로 탐색하는 방법입니다. 현재 정점을 A라 하고, A와 연결된 가선이 B라고 가정해 봅시다. A까지 이동하는 비용을 a , B까지 이동하는 비용을 b , A에서 B로 이동할 때 발생하는 비용 x 라 할 때a+x < b 라면B까지 가는 비용을 a+x로 갱신할 수 있습니다. 아래 예제를 통해 더 자세히 알아보겠습니다. 위와 같은 .. 2017. 10. 6. 이전 1 다음 반응형
