개발일지

개념 Short Path Faster Algorithm의 약어로 가장 빠른 경로를 찾는 알고리즘이다. 다익스트라 알고리즘은 음수인 간선이 존재할 때 사용할 수 없고, 벨만-포드 알고리즘보다 효율이 좋기 때문에 MCMF 알고리즘에서 많이 사용한다. 작동원리 isIn => 덱에 해당 정점이 있는지 확인하는 배열, 큐에 중복으로 값을 넣는 것을 방지 count => 업데이트된 횟수를 저장하는 배열, CYCLE을 확인할 수 있다.(벨만-포드와 같은 개념) 1. 시작 정점을 덱에 넣고 count, isIn, distance를 업데이트한다. 2. 덱에서 POP FRONT하고 isIn을 false로 업데이트한다. 3. 현재 정점에서 갈 수 있는 정점중 distance를 업데이트 할 수 있는 정점이 있으면 distan..