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