플로이드 워셜1 [알고리즘 개념] 최단경로 알고리즘 - 다익스트라, 플로이드 워셜, 벨만 포드 다익스트라 알고리즘 특정 노드에서 다른 노드(One To Any)로 가는 각각의 최단 경로 구하기 모든 vertex 사이의 edge의 cost는 음수가 아니어야 한다 -> 그렇기 때문에 실제 길 찾기 알고리즘으로 쓰인다 "가장 비용이 적은 vertex를 선택하여 경로 삼는 방식 -> 가장 작은 비용이 적은거를 기반으로 다음 노드를 선택하면 그 다음 노드도 결국 비용이 작은 것이다!!! " 따라서 알고리즘 분류를 한다면 greedy 알고리즘 에 속한다 준비 사항 최단 거리 배열 - 각 idx는 vertex를 가리키고 출발점에서 해당 vertex까지의 최단 거리 / 각 vertex에 대한 현재까지의 최단 거리 visited 배열 - 방문했는지 체크 과정 최단 거리 배열을 1e9 로 초기화 최단 거리 배열의 .. 2022. 3. 14. 이전 1 다음