n번째 최단경로..

  • CYPark
    CYPark

    n번째 최단경로..는 어떻게 구할 수 있을까요..?
    구글링을 해봐도 잘 이해가 안가네요..
    .ㅜㅜ

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]


    15년 전
7개의 댓글이 있습니다.
  • Toivoa
    Toivoa

    그래프에 cost가 음수인 간선이 없다면 Dijkstra 알고리즘을 응용해서 구할 수 있습니다. 자세한건 생각해보시고 추가로 질문해주시면 더 알려드리겠습니다. ^^


    15년 전 link
  • Toivoa
    Toivoa

    참고로 uva에 Not the best - http://acm.uva.es/p/v107/10740.html - 문제가 n번째 최단 경로의 cost를 찾는 문제입니다.


    15년 전 link
  • CYPark
    CYPark

    감사합니다.. 그런데 dijkstra알고리즘을 응용해서 구한다는게 감이 안오네요..;;


    15년 전 link
  • Toivoa
    Toivoa

    뜬구름 잡는 소리로 보일지 모르겠지만, Dijkstra에서 테이블에 저장하는 것은 가장 빠른 경로뿐입니다. 이 테이블을 n개의 경로를 저장할 수 있도록 확장해 보세요.


    15년 전 link
  • CYPark
    CYPark

    음 dist[i][k] : s->i까지의 k번째 최단경로..로 두고 테이블을 채운다는식인가요..??
    이게 맞다면 시간복잡도가 o( mk..) 이렇게 되나요,,?


    15년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    배열은 그런 식으로 잡으면 되고, 우선순위 큐를 이용하는 게 좋습니다. 그렇다면 시간복잡도는 O( E*n*log(E*n) ) 정도 될 것 같네요..


    15년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    음수 가중치가 있다면, 다익스트라가 제대로 동작하지 않겠죠..?
    벨만포드를 응용해야 되지 않을까 싶네요..


    15년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.