반응형 17532 C++ 다익스트라 개념과 예제-백준 1753번 다익스트라 알고리즘다익스트라 알고리즘은 그래프에서 최단거리를 구하는 알고리즘으로, 가중치 그래프에서 한 정점에서 다른 정점과의 최단거리를 구하는 알고리즘 입니다.다음과 같이 주어진 그래프를 인접리스트로 구현합니다. 한 노드에 대해 인접한 정점을 (노드번호, 거리) 튜플로 저장합니다.1 -> (2,8) (3,3)2 -> (4,4) (5,15)3 -> (4,13)4 -> (5,2)5위와 같이 인접리스트를 만든후, 최단 거리리스트를 초기화하고 탐색을 시작합니다.정점 1부터 출발한다고 가정하겠습니다. (INF는 무한대 입니다.)123450INFINFINFINF그 중 거리가 가장 짧은 1을 채택해서 탐색합니다.12345083INFINF1은 이제 탐색했으므로 방문여부 체크하고 다시 탐색하지 않습니다. 1을 제외한 .. 2024. 5. 15. 파이썬(Python) 다익스트라 개념과 예제-백준 1753번 다익스트라 알고리즘 다익스트라 알고리즘은 그래프에서 최단거리를 구하는 알고리즘으로, 가중치 그래프에서 한 정점에서 다른 정점과의 최단거리를 구하는 알고리즘 입니다. 다음과 같이 주어진 그래프를 인접리스트로 구현합니다. 한 노드에 대해 인접한 정점을 (노드번호, 거리) 튜플로 저장합니다. 1 -> (2,8) (3,3) 2 -> (4,4) (5,15) 3 -> (4,13) 4 -> (5,2) 5 위와 같이 인접리스트를 만든후, 최단 거리리스트를 초기화하고 탐색을 시작합니다. 정점 1부터 출발한다고 가정하겠습니다. (INF는 무한대 입니다.) 1 2 3 4 5 0 INF INF INF INF 그 중 거리가 가장 짧은 1을 채택해서 탐색합니다. 1 2 3 4 5 0 8 3 INF INF 1은 이제 탐색했으므로 .. 2022. 10. 14. 이전 1 다음
