7. 최단 경로 알고리즘 - 음주 운전 단속(drunken) 문제

문제를 해결하기 위해 각 장소를 정점으로 하고 도로를 간선으로 하는 그래프를 모델링할 수 있다.

그런데 중간 지점에서 음주 단속을 할 수 있기 때문에 최단 경로의 경유점이 중요하다.

따라서 플로이드 알고리즘을 약간 변형하여 문제를 해결하도록 한다.

플로이드는 경유점 집합을 늘려가며 모든 쌍에 대해 최단 경로를 구한다.

이 때 경유점 집합에 정점을 어떤 순서로 추가하든지 관계는 없다.

따라서 각 정점을 단속에 걸리는 시간 별로 정렬한 뒤, 시간이 적게 걸리는 정점부터 경유점 집합에 추가하면서 최단 경로를 갱신해나간다.

최단 거리를 계산하면서, 해당 최단 거리에 최대 지연 시간을 더한 값을 계산하여 이전의 어떤 경로보다 짧은지 비교하여 저장한다.

해당 경로에서 가장 단속이 오래걸리는 지점은 현재 경유하게 된 지점이 되기 때문에, 시간을 계산하기 편리하다.

u에서 v로 가는 최적의 경로에서 단속에 따른 지연시간이 가장 긴 정점을 w라고 하자.

그러면 이 때 u에서 v로 가는 최적 경로의 길이는 c[u][w] + c[w][v] + delay[w] 가 된다.

이 점화식을 이용해서 알고리즘을 구현 할 수 있다.

// 음주 운전 단속 문제를 해결하는 플로이드 알고리즘

int v;

int adj[500][500];

int delay[500];

int w[500][500];

void floyd(){

// 모든 정점을 단속 지연 시간 기준으로 오름차순 정렬한다.

vector< pair<int, int> > order;

for(int i = 0; i < v; i ++){

order.push_back(make_pair(delay[i], i));

}

sort(order.begin(), order.end());

for(int i = 0; i < v; i++){

for(int j = 0; j < v; j++){

if(i == j) w[i][j] = 0;

else w[i][j] = adj[i][j];

}

}

for(int k = 0; k < v; k++){

int w = order[k].second;

for(int i = 0; i < v; i++){

for(int j = 0; j < v; j++){

adj[i][j] = min(adj[i][j], adj[i][w] + adj[w][j]);

w[i][j] = min(w[i][j], adj[i][w] + delay[w] + adj[w][j]);

}

}

}

}