2개의 댓글이 있습니다.

• 
  Being

  1. 일반적인 그래프라면 모든 쌍에 대해 최단 경로를 구해야 하고, 가중치가 없는 그래프라면 BFS로도 최단 경로를 구할 수 있으니 맞습니다.
  2. 일단 Dijkstra's Algorithm을 V번 돌리는 것과 비교해서 생각해 보시면 되겠습니다. 모든 쌍 간의 최단 거리는 Dijkstra's Algorithm을 V번 돌리는 것만으로도 충분히 구할 수가 있지요. 이 알고리즘의 의미는 음수 가중치가 싸이클만 없다면 허용된다는 데 있는데요, 프로그래밍 대회에서는 아직까지 본 적은 없네요. 보시다시피 간단한 알고리즘은 아니라서 ㅎㅎ

  
  11년 전 link

• 
  Being

  덧붙이자면 Floyd-Warshall 로도 음수 엣지는 처리할 수 있기 때문에, 음수 엣지가 있으면서 sparse라는 특수한 상황에서나 의미가 있습니다. 이런 문제를 내는 건 이 알고리즘 아는지 모르는지에 대한 단편적인 지식을 묻는 모양이 되기 쉬워서 드물지요.

  
  11년 전 link

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