알고리즘 유형

참고:\[이것이 코딩 테스트다 with Python] 30강 다익스트라 최단 경로 알고리즘 다익스트라 알고리즘(Dijkstra's Algorithm):한 노드로부터 다른 모든 노드까지의 최단 경로를 찾을 때 사용되며, 가중치가 양수인

주어진 가중치 그래프의 모든 정점을 최소한의 비용으로 연결하는 부분 그래프를 의미한다.주로 크루스칼(Kruskal) 알고리즘 또는 프림(Prim) 알고리즘을 사용해서 해결할 수 있다.가장 가벼운 가중치를 가진 간선부터 선택하면서 MST를 구성한다.최종적으로 선택될 간선

모든 정점에서 모든 정점으로의 최단 경로를 구한다.다익스트라 알고리즘이 가장 적은 비용부터 하나씩 선택하는 특징이 있는 반면,플로이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 알고리즘을 수행하는 특징이 있다.다익스트라 알고리즘은 다이나믹 프로그래밍을 기반으로 한다.2차