Floyd-Warshall
3중 for문으로 i 노드에서 j 노드로 가는 비용을 모든 노드(k)를 경유해서 간다고 했을 때의 금액과 비교하여 최소값으로 바꾸는 방법으로 경유 노드인 k를 가장 바깥 for문으로 해야만한다.
Dijkstra
다익스트라 알고리즘은 start 노드를 기준으로 각 노드까지의 비용을 저장하는 list를 만들어 업데이트 해나가는 방식을 사용한다.
첫 for 문을 신경쓰지말고 start가 이미 정해졌다고 생각하고 보면 편하다.
bfs 방식으로 현재 방문한 노드를 기준으로 원래 처음에 구한 비용보다 최신화되어 더 작아진 적이 있다면 굳이 조회할 필요 없다.
그렇지 않다면, 방문한 노드에서 연결된 노드들을 보고 그 노드들까지의 비용을 구한다.(방문한 노드까지의 비용 + 간선의 가중치) 이 값이 기존의 최소 비용보다 작다면 업데이트 해주고, 업데이트 했다면, 해당 노드만 추가해준다.
(업데이트하지 않았다면 방문 노드에서 새 노드까지 가는 경로중 최소 경로가 아니라는 의미이므로 추가해서 볼 필요가 없다. 이를 통해 visited를 사용하지 않고 풀 수 있다.)
모든 노드를 start 노드로하여 n개의 list를 구하고, 이를 통해 마지막으로 경유하는 노드 별로 금액을 구해서 최소가 되는 값을 최종 출력하는 방식이다.
플로이드 워샬 방식에 비해 대체적으로 빠르다.
ML Engineer