sksdong1   3달 전

jm북에 있는 음주운전 문제 개념을 참조해서 풀었는데요,

이 문제에서 멍멍이로 인한 패널티를 오름차순으로 정렬해서

패널티가 작은 정점부터 경유하면서 거리를 갱신하잖아요

패널티가 큰 정점을 먼저 방문했을 때 패널티가 작은 정점이 최적의 경우가 유지가 안되는 이유가 잘 이해가 안가네요

패널티가 큰 정점을 먼저 방문해서 만들어진 경로가 패널티가 작은 정점을 방문했을 때 어떤 영향을 미치나요??

kks227   3달 전

플로이드 알고리즘의 구조가 k번째 루프에 정점 0~k번을 사용해 갈 수 있는 최단거리를 갱신하는데,

이 문제에서는 최단거리에다가 이 경로를 거치는 정점들 중 가장 큰 패널티값까지 더해야 하고 그 결과들 중 가장 작은 걸 찾아야 합니다.

때문에 경로 중에서 가장 큰 패널티값이 문제인데,

k번째로 패널티가 작은 정점을 사용해서 최단거리 및 W 배열을 갱신하면 W[i][j]를 w를 우회하는 경로로 갱신할 때 max(delay[i],max(delay[j],delay[w])) 구문처럼 i, j, w의 패널티 정보만 가지고도 갱신할 수 있게 됩니다.

왜냐면 i, j, w 정점의 패널티 중 최댓값만 보아도, 이 경로상에서 가장 큰 패널티값을 알 수 있기 때문입니다.

지금까지는 w보다도 패널티가 적은 정점들만을 사용해서 최단거리를 갱신해 왔으므로, 만약 이번에 w를 추가로 지나서 새로운 최단 경로를 갱신한다면 그 경로상의 정점들 중 가장 패널티가 큰 정점이 w일 것이기 때문이죠.

댓글을 작성하려면 로그인해야 합니다.