SPFA (Shortest Path Faster Algorithm)

SPFA(Shortest Path Faster Algorithm) 라는 알고리즘은 벨만-포드 알고리즘과 유사하게 음수 가중치가 있을 때 사용가능한 단일 시작점 알고리즘입니다.

 

2020/09/07 - [알고리즘] - 벨만포드 알고리즘

 

벨만-포드 알고리즘은 총 E 개의 간선을 V 번 방문을 해서 O(VE) 의 시간 복잡도를 갖습니다.

하지만 SPFA 는 경로의 길이가 갱신된 정점에 인접한 간선에 대해서만 다음 방문에서 체크를 하기 때문에 같은 간선을 V 번 방문할 필요가 없어서 평균 시간 복잡도가 O(E) 입니다.

 

단, 경로의 길이가 갱신되지 않았다면 방문을 계속 해야하기 때문에 최악의 경우엔 O(VE) 의 시간 복잡도를 갖습니다.

 

 

SPFA 의 동작 원리는 벨만-포드 알고리즘의 동작 원리와 비슷하므로 차이점 중심으로 말씀드리겠습니다.

---

위 그림은 벨만-포드 알고리즘을 설명드릴 때 사용했던 그래프입니다.

벨만-포드 알고리즘에서는 모든 정점을 순차적으로 방문하여 각 정점에 인접한 간선을 타고 간선과 연결된 정점까지의 최단 경로를 갱신해 나아가는 방식이었습니다.

 

그러나 앞에서의 설명에 따르면 벨만-포드 알고리즘은 경로의 길이가 갱신된 정점에 인접한 간선만을 방문해야 하니 해당 정점만을 따로 모아둘 필요가 있습니다.

 

SPFA 는 위 정점들을 큐에 저장하며 각 정점을 V번 방문하는 것이 아니라 더 이상 방문할 정점이 없어지는 시점, 즉, 큐가 비워질 때 함수를 종료하면 되겠습니다.

 

이를 소스코드로 알아봅시다.

---

#define MAX 987654321
int V,E,u,v,w;
vector <pair<int, int> >adj[V_Max];
//메인함수에서 간선을 저장할 벡터를 만들어놓습니다.

vector<int> SPFA(int src){

	vector<int> dist(V, MAX);
    //최단경로의 길이를 저장할 벡터입니다. 초기값은 MAX입니다.
    
	queue<int> q;
    //방문할 정점을 저장할 큐를 생성합니다.
    
	bool inQ[V] = {};
    //O(1) 시간만에 큐에 특정 정점이 있는 판단하기 위한 배열 생성
    
	int visit[V] = {};
    //특정 정점을 몇번 방문했는지 알기 위한 배열 생성
    
	dist[src] = 0;
    //시작점에서 시작점으로의 최단경로는 0으로 설정해둡니다.
    
	q.push(src); inQ[src] = true;
    //시작점을 방문할 정점 목록에 넣습니다. 

	++visit[src];
    //시작점을 한번 방문했다고 기록합니다.
    
	while(!q.empty()){
    //방문할 정점이 남지 않을 때까지 반복합니다.
    
		int here = q.front();Q.pop(); inQ[here] = false;
        //큐에서 방문할 정점 하나를 뽑습니다.
        
		for(int num = 0;num < (int)adj[here].size();num++){
        //현재 정점에 인접한 정점을 방문해봅니다.
        
			int there = adj[here][num].first;
            //인접한 정점의 번호
                
            int cost = adj[here][num].second; 
            //인접한 정점으로 가기위한 가중치
            
			if (dist[there] > dist[here] + cost) {
                //인접한 정점으로 방문할 때, 최단경로가 짧아진다면
                
				dist[there] = dist[here] + cost;
                //경로의 길이를 갱신하고
                
				if(!inQ[there]){
                //인접한 정점이 큐에 없다면
                
					Q.push(there);inQ[there] = true;
                    //큐에 배열을 넣어놓고
                    
					if(++visit[there] >= V)
                    //해당 정점을 V번 이상 방문했다면 음수 사이클이 있다는 의미이므로
                    
						return vector<int>();
                        //빈 벡터를 반환합니다.
				}
			}
		}
	}
	return dist;
    //음수 사이클없이 큐가 비워졌다면 성공적으로 최단 경로 길이를 담은 벡터를 반환합니다.
}

---

최단 경로 알고리즘 중 SPFA 에 대한 포스팅이었습니다.

오타 지적과 조언은 언제나 환영입니다.