다익스트라

[Algorithm/Python] 다익스트라 최단 경로 알고리즘이란? || dijkstra

들어가며 본 포스팅에서는 다익스트라 최단 경로 알고리즘에 대해 소개합니다. 📌 다익스트라 최단 경로 알고리즘이란? 다익스트라 최단 경로 알고리즘이란, 가장 짧은 경로를 찾기 위한 알고리즘으로, 음의 간선(0보다 작은 값을 가진 간선)이 없을 때에 적용할 수 있는 알고리즘입니다. 1️⃣ 출발 노드를 설정합니다. 2️⃣ 최단 거리 테이블 초기화(무한으로 설정)합니다. 3️⃣ 방문하지 않은 노드 중에 최단 거리 테이블에서 최단 거리가 가장 짧은 노드를 선택합니다. 4️⃣ 선택한 노드를 거쳐 다른 노드로 가는 거리를 계산합니다. 5️⃣ 계산된 거리가 최단 거리 테이블의 거리보다 짧을 경우, 갱신합니다. 6️⃣ 위의 3️⃣4️⃣5️⃣를 반복합니다. 가장 최단 거리의 노드를 선택하여 주변 간선을 확인합니다. 더 짧..