플로이드 알고리즘의 Drunken 문제 관련 질문 nicelhc13 이 질문은, 알고리즘 문제해결전략2의 963page 관련 질문입니다. 아무래도 스포일러의 여지가 있다고 판단되어,,, 감추어 질문드리겠습니다. 이 문제를 풀 때, 'u에서 v로 가는 최단 시간'을 W[u][v] 라고 가정하고, W[u][v] = minCw(u, w) + Cw(w, v) + Ew 인데, 이 식이 헷갈립니다. 예를 들어, 예제 그래프의 경우 node #1에서 node #5로 갈 때, 답의 경로는 node #2와 node #3을 단방향으로 경유할 것입니다. 그리고 이 문제에서 물어보는 것은, node#1 ~ node#5 사이 걸리는 시간 중 최악의 상황을 물어봅니다. 따라서 당연히 node #2에서 음주 단속을 하는 경우가 최악의 경우일 것입니다. 하지만 책에 설명에 의하면, w가 node #2(delay: 6), node #3(delay: 5) 인 경우를 각각 계산할 것인데, 경유지로써 node #3 을 선정하기 전에 먼저 node #2를 선정할 것입니다. 따라서 min연산을 수행한다면, ndoe #3을 경유지로써 선정될 때 node #2를 경유지로 했을 때 기록을 지울 것입니다. (node#2를 경유지로할 때는 3+6+6+2 = 17이고, node #을 경유지로 하면 3+6+5+2=14이기 때문입니다.) 그렇다면 node #1에서 node #5까지 경로의 최악의 경우라고 할 수는 없을 것 같은데, 제 생각의 맹점이 무엇일까요?? 조언해주시면 감사하겠습니다! 5년 전
0개의 댓글이 있습니다. 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
nicelhc13
이 질문은, 알고리즘 문제해결전략2의 963page 관련 질문입니다.
아무래도 스포일러의 여지가 있다고 판단되어,,, 감추어 질문드리겠습니다.
이 문제를 풀 때,
'u에서 v로 가는 최단 시간'을 W[u][v] 라고 가정하고,
W[u][v] = minCw(u, w) + Cw(w, v) + Ew
인데,
이 식이 헷갈립니다.
예를 들어, 예제 그래프의 경우
node #1에서 node #5로 갈 때,
답의 경로는 node #2와 node #3을 단방향으로 경유할 것입니다.
그리고 이 문제에서 물어보는 것은,
node#1 ~ node#5 사이 걸리는 시간 중 최악의 상황을 물어봅니다.
따라서 당연히 node #2에서 음주 단속을 하는 경우가 최악의 경우일 것입니다.
하지만 책에 설명에 의하면,
w가 node #2(delay: 6), node #3(delay: 5) 인 경우를 각각 계산할 것인데,
경유지로써 node #3 을 선정하기 전에 먼저 node #2를 선정할 것입니다.
따라서 min연산을 수행한다면, ndoe #3을 경유지로써 선정될 때
node #2를 경유지로 했을 때 기록을 지울 것입니다. (node#2를 경유지로할 때는 3+6+6+2 = 17이고, node #을 경유지로 하면 3+6+5+2=14이기 때문입니다.)
그렇다면 node #1에서 node #5까지 경로의 최악의 경우라고 할 수는 없을 것 같은데,
제 생각의 맹점이 무엇일까요??
조언해주시면 감사하겠습니다!
5년 전