개발관련/알고리즘(Algorithm)1 플로이드워셜(FloydWarshall) 알고리즘 FloydWarshall 알고리즘 FloydWarshall(플로이드워셜) 이란 그래프에서 모든 정점에서 모든 정점으로의 최단경로를 구하는 알고리즘 시간복잡도 O(N^3) 한 출발점에서 어떤 한 도착점까지 갈 수 있을 때, 갈 수 있는 경로 중 최단경로가 되는 값을 구한다 출발점과 도착점 사이의 경유지를 거쳐갈 경우를 고려해 최단경로를 파악한다 ex) 2 -> 4로 갈 수 있는 경로. 2->3->4(11) , 2->1->4(9) 이므로 9가 선택되야함. 사진출처 : kdb.velog FloydWarshall(플로이드워셜) 구현 방법 2차원 배열에 그래프의 간선 정보를 저장 (직접 연결되어 있지 않으면 무한, 자기 자신으로 가는 거리 0) for(int i=0;i 2021. 7. 11. 이전 1 다음
