Persistence

다익스트라 알고리즘(Dijkstra's algorithm) 최단 시간 경로 너비 우선 탐색이 최단 경로(가장 짧은 단계)였던 반면, 다익스트라 알고리즘은 가장 빠른 경로 즉, 최단 시간 경로를 탐색한다. 다음과 같은 단계를 거친다. 가장 가격이 "싼" 정점을 찾는다. 가장 가격이 싼 정점이란 도달하는 데에 걸리는 시간이 가장 짧은 정점을 말한다. 이 정점의 이웃 정점들의 가격을 조사한다. 그래프 상의 모든 정점에 대해 이 일을 반복한다. 최종 경로를 계산한다. 예시 위 그래프에서 A까지 가는 시간은 6, B까지 가는 시간은 2이므로 B가 가장 싼 정점이다. 이 때 도착점까지 얼마 걸리는 지는 알 수 없으므로 무한대라고 한다. 정점 B의 이웃 정점의 가격을 조사한다. B에서 A를 가는 시간은 3이므로 출발..