🗺️ 다익스트라 최단경로
내비게이션이
가장 빠른 길을 찾는 방법
도시 여러 개가 도로로 연결되어 있어요. 출발지에서 도착지까지 가장 짧은 경로를 어떻게 찾을까요? 다익스트라 알고리즘은 "지금까지 알려진 가장 가까운 도시"부터 차례로 확정해가며, 결국 최단 거리를 찾아내요.
동작 방식: 출발지 거리를 0으로 두고 나머지는 무한대로 시작해요. 매번 "아직 확정 안 된 도시 중 거리가 가장 짧은 곳"을 확정하고, 그 도시를 거쳐가면 이웃 도시까지의 거리가 더 짧아지는지 확인해서 갱신해요. 모든 도시가 확정될 때까지 반복해요.
출발·도착 도시를 고르고 시작해보세요
💡 실제 지도 앱의 길찾기, 인터넷 데이터가 최적 경로로 전달되는 라우팅까지 전부 이 알고리즘(또는 그 친척)을 바탕으로 만들어져 있어요.