1개의 댓글이 있습니다.
-
-
JongMan -
최단 경로를 계산할 때는 차이가 없죠. 이 문제 (경로 길이 + 정점 가중치를 최소화)를 풀 때는 차이가 있습니다. 정점들을 정렬했는데 검사 시간이 10,20,30,40 이었다고 합시다. 이 순서대로 갱신을 하면, 30 정점을 사용하는 최단 경로를 계산할 때 이 경로 상에서 최대 검사 시간은 30이겠죠. 아직 40을 사용하는 경로를 계산하지 않았으니까요. 알고리즘이 진행됨에 따라서 우리가 찾은 시작점-도착점 사이의 최단거리는 감소하고 (더 짧은 경로를 찾으니까) 이 정점 중의 최대 정점 가중치는 증가합니다 (더 가중치가 큰 정점들을 사용하니까) 알고리즘 진행하면서 이 둘의 합 중 최소값을 찾으면 됩니다.
7년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
sksdong
음주운전 단속 문제에서요
정점에서 소요되는 시간이 작은 순으로 정렬한 다음에
시간이 작게 소요되는 정점부터 경유점에 포함을 하는데
이게 잘 와닿지가 않아서요.
플로이드 알고리즘은 경유점을 늘려나갈 때 순서는 중요하지 않다는건
어차피 어느 모든 정점에 대한 갱신이 이뤄지기 때문이잖아요?
그래서 위 문제에서도 정점에 소요되는 시간별로 정렬하지 않더라도
어차피 모든 정점에 대해 갱신이 될 거 같은데 (물론 이렇게 답이 안나오는건 확인했습니다.)
어렴풋이는 알겠는데 확 와닿지가 않네요..
랜덤하게 할 때랑 정렬해서 할 때 어떤 차이가 있는건가요/?
7년 전