회사와 일상 그 사이
느리게 가는 내비게이션
얼마전에 티맵에서 느리게 가는 네비게이션이 나왔다는 뉴스를 봤다. “주변 경치 감상하면 천천히”…느리게 가는 내비게이션 출시 제일기획, 제주도 등과 함께 ‘슬로우로드’ 내비게이션 서비스…‘빠른 길’ 대신 ‘관광지 경유’ 추천내비게이션이.. www.munhwa.com 보통 내비게이션하면 최단 거리를 구하고, 최단 거리 알고리즘 중에 가장 유명한 것은 다익스트라 알고리즘이다. 다익스트라 알고리즘은 그리디알고리즘으로 그래프의 노드 탐색할 때 BFS를 이용한다. 다익스트라 알고리즘은 가중치가 음수인 경우 처리할 수 없어다. 왜냐면 다익스트라 알고리즘은 항상 노드 주변의 최단 경로를 선택한다. 즉, 이미 최단 경로로만 왔는데 더 짧은 경로가 존재했다면 다익스트라 알고리즘의 논리가 무너진다. 그래서 음수 가중치가 ..
