최단 경로. [11404]

[1. 문제 설명]

N 개의 정점에 M 개의 edge 가 있을 때,

모든 도시 쌍 (A, B) 에 대해서 A에서 B로 가는데 필요한  최소비용을 출력한다.

 

 

 

[2. 풀이 접근]

1. 다익스트라 알고리즘
   => 정점의 개수는 edge 의 개수에 비해 무시할 수 있으므로 (계산 편리성을 위해),
   이 문제에서 다익스트라 시간 복잡도는 O(ELogV), 최대 O(100000*7)
   => 필요한 전체 경로 개수 N^2, 최대 10000
   => 전체를 구해야 할 때, (10^4)*(10^5)*7 == 7*10^9
   => 대략 7초, 시간 초과 발생 가능성이 높음 

 

플로이드-워셜 알고리즘 (위키피디아 참조)

[A. 개요]

edge 의 가중치가 음이거나 양인 (음수 사이클이 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘

(문제 입력 조건에서 음수 weight 가 없다. => 음수 사이클이 없음을 보장하는 것)

알고리즘을 한 번 수행하면 모든 정점들의 최단 경로 길이를 찾을 수 있다.

(알고리즘 자체는 경로를 반환하지 않는다.)

 

 

[B. 동작방식]

작성해야 함...

 

 

[C. 시간복잡도]

V 가 정점의 개수 일 때,

 

O(V^3)

 

 

 

[3. 코드]