플로이드 와샬(Floyd Warshall) 알고리즘

플로이드 와샬 알고리즘은 모든 각각의 노드를 출발점으로해서 모든 정점까지의 최단경로를 구하는 알고리즘입니다. 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택해야 했다면 플로이드 와샬 알고리즘은 기본적으로 '거쳐가는 정점'을 기준으로 알고리즘을 수행한다는 점에서 그 특징이 있습니다. 플로이드 와샬은 기본적으로 다이나믹 프로그래밍 기술을 활용합니다. 프로그래머스의 합승 택시 요금 문제가 플로이드 와샬을 활용할 수 있는 문제이다. 문제의 풀이 코드로는 아래와 같다. function solution(n, s, a, b, fares) { let dp = new Array(n).fill().map((_,i)=>new Array(n).fill().map((_,j)=>i===j ? 0 : Infinity)); fa..

2023.03.31