플로이드 알고리즘의 Drunken 문제 관련 질문

  • nicelhc13
    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까지 경로의 최악의 경우라고 할 수는 없을 것 같은데,

    제 생각의 맹점이 무엇일까요??
    조언해주시면 감사하겠습니다!


    4달 전
0개의 댓글이 있습니다.
  • 댓글을 남기시려면 로그인하세요.