최단 경로 정의

최단 경로는 w(p) = d(u, v) 가 되는 경로를 의미한다.
정점 u에서 정점 v로 가는 경로 중에, 경로 p에 대한 가중치 값이 최소인 경로

단일 출발지 최단 경로

몇가지 변형들

  • 단일 도착지 최단 경로 : 간선을 모두 뒤집으면 단일 출발지로 변경됨
  • 단일 쌍 최단 경로 : u->v 쌍일때, u에서 출발하기로 풀면 됨
  • 모든 쌍 최단 경로 : 정점마다 단일 출발지로 다 하면 되지만 더 좋은 알고리즘이 존재

최단 경로의 최적 부분 구조

최단 경로가 그 안에 다른 최단 경로를 포함한다는 특성
부분 경로A가 최단 경로가 아니라면 해당 부분 경로A 말고 다른 최단 경로 B를 선택하면 되기 때문이다.

음의 가중치 간선

음의 가중치 순환 구조인 경우 해당 순환만 반복하면 가중치가 계속 작아지기 때문에 최단 경로를 구할 수 없게 된다.

최단 경로는 V-1개 간선을 가진 단순 경로.

  • 음의 순환 포함하지 않는다.
  • 양의 순환의 경우는 순환만 제거하면 최단 경로
  • 가중치 0일 경우는 제거 하면 최단 경로

완화(relax)

v.d를 최단경로 추정값이라고 하면 (최단 경로로 가는 것을 예상)
완화하는 과정은 (u,v)간 d를 개선한지 검사와 갱신하는 것

if v.d > u.d + w(u,v) // 검사
    v.d = u.d+w(u,v)  // 갱신
    v.p = u           // 직전 원소 ( 최단 경로 트리)

최단 경로와 완화의 특성

  • 삼각 부등식
    임의의 간선 (u,v)에 대해 d(s,v) <= d(s,u)+w(u,v)
  • 상한 특성
    v.d 가 갱신하다가 최단 경로에 도달(상한)하면 더 이상 변하지 않는다.
  • 무경로 특성
    경로가 없으면 v.d는 항상 초기값 (경로가 있을때만 갱신)
  • 수렴 특성
    s->u->v 에서 u.d가 최단 경로만 (u,v)완화 이후 항상 v.d도 최단 경로
  • 경로 완화 특성
    최단 경로 p에 각 간신들은 순서대로 하면 마지막 정점도 최단경로가 된다. (P 간선 순서 상관없이도 가능)
  • 직전원소 부분 그래프 특성
    v.d가 최단 경로가 되면 s를 루트로 갖는 최단 경로 트리 구성
최단 경로와 완화의 특성 증명

벨만-포드 알고리즘

가중치가 음수인 일반적인 경우에도 단일 출발지 최단 경로 문제를 해결할 수 있음

// 각 정점에 대해 V-1번 반복하여 완화과정 거침
for i = 1 ~ V-1
    for 각 간선
        relax(u,v,w)

// 한번 더 검사, 각 간선이 최단거리가 되었는데 또 갱신이 되면 음의 순환이 있다는 것
for 각 간선
    if v.d > u.d + w(u,v)
        return false;
return true;

시간 : O(VE)

V-1번 반복하면 모든 정점 v에 대해 v.d가 최단경로가 된다.
최단 경로는 단순 경로로 최단 경로 p는 v-1개의 간선을 가진다.
각 반복이 E개 모든 간선을 완화시키기 때문에.
경로 완화 특성에 의해 v-1번 반복하면 임의의 정점에 대해 최단 경로를 가질 수 있다

다시 한번 검사했을때 완화 갱신이 되면, 음의 순환이 있는 경우뿐
음의 순환은 계속 반복할 수록 가중치가 낮아지기 때문

방향 비순한 그래프

위상 정렬 순서로 완화하면 최단 경로를 O(V+E) 만에 구할 수 있음
경로 완화 특성에 의해 성립함

다익스트라 알고리즘

간선의 가중치가 음이 아닌 경우에 최단 경로 문제 풀 수 있음.

우선순위 큐를 이용하여 프림알고리즘 처럼 해결한다.
경로 완화 특성을 이용함.
최단거리로 그리디 하게 찾아서 갱신
벨만 포드는 모든 정점을 갱신하기 때문에 속도가 느림

light edge를 추가하면 안전하다는 아이디어.

While(!q.empty())
	u = extract_min(q)
	s = s U {u}
	for u에 인접한 각 정점
		relax(u,v,w)

S집합에 더해지는 간선은 완화하면 최단경로로 된다
S집합에서 V-S에 있는 정점 중에 간선의 가중치가 작은 것을 선택
경로 완화 특성에 의해 S에 더해질때 최단 경로가 됨

음의 가중치가 있으면 최단 경로가 안될 수 있음
V-S에서 respect인 간선이 음의 간선이라면 S에 더해질때
u->v->w 가 최단 경로인데 u->w로 바로 S집합에 더해질 수 있음

우선순위 큐에 따라 수행시간이 달라짐
Sparse 그래프( 밀도 낮은)라면 이진 최소 힙 O(V^2/lgV)
피보나치 힙 O(VlgV + E)

SPFA 알고리즘

다익스트라와 비슷한 아이디어
다익스트라는 우선순위 큐로 최소 간선을 담았다면,
SPFA는 경로 완화가 될 경우에만 큐에 간선을 추가하는 방식
평소 다익스트라 보다 더 빠르게 동작함

다익스트라는 light edge라 괜찮은데, 먼저 찾는 edge로 v를 Q에 넣어도 되는가?
Q에는 안넣고 완화하는 작용은 함. 
Q는 서로 다른 Layer가 최대 1개이기 때문에 v가 Q에서 나올때는 v.d가 갱신되어 최단거리로 완화했음.
// 출발점이 아닌 정점들 초기화
for each vertex v != s in V(G)
    d(v) = INF
d(s) = 0
q.push(s)
while(!q.empty()){
    u = q.pop();
    for each edge(u,v) in E(G)
        if d(u)+w(u,v) < d(v)
	    d(v) = d(u)+w(u,v)
	    if v is not in Q
	        q.push(v)
}

SPFA의 평균적인 시간복잡도는 O(E)이지만, 최악에는 O(VE)이다.

모든 쌍의 최단 경로

플로이드-워샬 알고리즘

알고리즘 평균 시간 (V^3)

최단 경로 구조

최단 경로의 “중간” 정점을 고려.
중간 정점 : 경로 p에서 시작,출발을 뺀 나머지 정점들.
경로 p와 중간 정점 집합{1..k-1}의 최단 경로 관계 이용.

정점 집합이 {1..k-1}인 이유.
(1) 중간 정점이 k가 아니면, 경로 p의 중간 정점 집합은 k를 뺀 {1..k-1}가 됨.
(2) 중간 정점이 k이면, 경로 p = i->k->j 가 되는데 p1(i->k) 경로는 중간 정점 집합은 k를 뺀 {1..k-1}가 되고, 마찬가지로 p2(k->j)도 그렇다.

i->j에서 중간 정점 집합{1..k}에 대한 최단 경로는 k가 추가 되기전 중간 정점 집합{1..k-1}에서 k가 중간 정점일 때(2)와 아닐 때(1)의 최소값.
d_k = min(d_(k-1), p1_(k-1) + p2(k-1));

// proto-type
// c[k][i][j] 메모리 V^3
void floyd(){
    // 초기화
    for(int i = 0; i < V; ++i)
    for(int j = 0; j < V; ++j)
        if(i != j)    c[0][i][j] = min(adj[i][j], adj[i][0]+adj[0][j])
        else          c[0][i][j] = 0;
	
    for(int k = 1; k < V; ++k)
    for(int i = 0; i < V; ++i)
    for(int j = 0; j < V; ++j)
        c[k][i][j] = min(c[k-1][i][j], c[k-1][i][k]+c[k-1][k][j]);
}

// 메모리 줄이기 V^2
// k-1, k 만 알고 있으면 됨.
// c[k][i][j] 다 사용할 필요없이 c1[i][j], c2[i][j] 이렇게 가능
// 인접행렬에 가중치에 덮어 쓸수도 있다. 
// c[i][j]를 계산하기 위해 c[i][k], c[k][j] 만 사용하기 때문
// 출발점이나 도착점이 k인 최단 경로에 대해서는 덮어 쓸수 있다. (k-1이나 k나 아무 의미가 없음)
void floyd(){
    for(int i = 0; i < V; ++i) adj[i][j] = 0;
    
    for(int k = 0; k < V; ++k)
    for(int i = 0; i < V; ++i)
    for(int j = 0; j < V; ++j)
        adj[i][j] = min(adj[i][j], adj[i][k]+adj[k][j]);
}

실제 경로 계산

마지막에 갱신할때 k값을 저장해 두면 된다.
중간 정점 k를 찾으면 i->k, k->j로 쭉쭉 가면 됨.

int via[MAX_V][MAX_V];
void floyd2(){
    for(int i = 0; i < V; ++i) adj[i][j] = 0;
    memset(via, -1, sizeof(via));
    
    for(int k = 0; k < V; ++k)
    for(int i = 0; i < V; ++i)
    for(int j = 0; j < V; ++j){
        if(adj[i][j] > adj[i][k]+adj[k][j]){
	    via[i][j] = k;
	    adj[i][j] = adj[i][k]+adj[k][j];
	}
    }
}
void reconstruct(int u, int v, vector<int>& path){
    if(via[u][v] == -1){
        path.push_back(u);
	if(u != v) path.push_back(v);
    }
    else{
        int w = via[u][v];
	reconstruct(u, w, path);
        path.pop_back();        // w가 중복으로 들어오기 때문에 지움
	reconstruct(w, v, path);
    }
}

도달 가능성 확인(이행적 폐쇄)

i->j 경로가 도달 가능한지 여부 판단.

min(adj[i][j], adj[i][k]+adj[k][j])의 식에서
‘min’ => OR연산(둘 중에 하나면 연결되면 됨)
‘+’ => AND연산(i->k, k->j 는 둘다 연결되야 됨)
으로 치환