tech.log tech.log

최단 경로 알고리즘 - 가장 짧은 경로를 찾는 알고리즘이다. '길 찾기' 문제라고도 불린다. - 대표적으로는1. '한 지점에서 다른 특정 지점까지 최단 경로를 구해야 하는' 다익스트라 알고리즘2. '모든 지점에서 다른 모든 지점까지 최단 경로를 모두 구해야 하는' 플로이드 워셜 알고리즘이 있다. - 보통 '그래프' 를 이용해 표현된다.1. 각 지점은 '노드'로 , 연결된 도로는 '간선'으로 표현된다 다익스트라 알고리즘- 특정 노드에서 다른 특정 노드로 가는 각각의 최단 경로를 구해주는 알고리즘- 음의 간선(0보다 작은 값을 가지는 간선) 이 없을 때 사용- 현실 세계의 gps 알고리즘으로 채택된다 -> 현실세계에서는 음의 간선이 없으므로 가능- 매 단계 가장 비용이 적은 노드를 선택해서 과정을 반복하므로..