7개의 댓글이 있습니다.

• 
  Toivoa

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

  
  14년 전 link

• 
  Toivoa

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

  
  14년 전 link

• 
  CYPark

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

  
  14년 전 link

• 
  Toivoa

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

  
  14년 전 link

• 
  CYPark

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

  
  14년 전 link

• 
  Taeyoon_Lee

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

  
  14년 전 link

• 
  Taeyoon_Lee

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

  
  14년 전 link

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