최단 경로 Shortest Path 보통 그래프를 이용해서 표현 지점은 노드, 도로는 간선 e.g. 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 다익스트라 최단 경로 알고리즘 Diikstra 특정 노드에서 출발해서 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것 음의 간선이 없을 때 정상적으로 작동 GPS 소프트웨어의 기본 알고리즘으로 주로 채택 그리디 알고리즘 인접 리스트 이용 -> 노드와 연결된 모든 간선에 대한 정보를 리스트에 저장 알고리즘 원리 1) 출발 노드 설정 2) 최단 거리 테이블 초기화(무한) 3) 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택 4) 해당 노드 거쳐 다른 노드로 가는 비용 ..