spfa (1) 썸네일형 리스트형 118. Shortest Path Faster Algorithm Shortest Path Faster Algorithm(SPFA)은 벨만-포드 알고리즘을 약간 변형한 것으로 간선을 확인할 때 $d_v$의 값이 변하지 않았을 경우 그 정점과 인접한 정점을 다음 차례에 바로 확인할 필요가 없다는 성질을 이용한다. 작동 방식은 다음과 같다. 시작 정점은 $k$, 정점 $k$로부터 정점 $i$까지의 최단 거리를 $d_i$라고 한다.정점 $x$에서 정점 $y$로 가는 가중치 $z$인 간선이 존재할 때 $w(x, y) = z$라고 한다.$d_k$는 $0$, 나머지 $d_i$는 모두 $\infty$로 초기화한다.빈 큐에 정점 $k$를 추가한다.큐에서 정점 하나를 뺀다. 이 정점을 $u$라고 하자.$u$에서 나가는 간선이 존재하는 각각의 정점 $v$에 대해 $d_u + w(u, v.. 이전 1 다음
