최소경로

오랜만에 알고리즘을 잡으니 최소경로와 최소신장이 헷갈리고 기억도 잘 안나서 정리를 해본다. # 용어 최소경로 가중치가 없다 bfs 가장 먼저 도착하는게 최단 도착하자마자 끝내면 된다 가중치가 있다(완탐) 하나의 시작 정점에서 끝 정점까지의 최단 경로 다익스트라(dijkstra) 음의 가중치 허용x 벨만 포드(Bellman-Ford) 음의 가중치 허용 모든 정점들에 대한 최단 경로 플로이드-워샬(Floyd-Warshall) 따지고보면 다익스트라를 N만큼 반복해줘도 된다 실제로 시간복잡도도비슷하게 나옴 다익스트라Dijkstra 방식 그리디하게 진행된다. 시작점으로부터 가장 저비용인 곳을 선택하면서 최단 경로를 알아낸다. 그리디하게 해결 가능한 이유 음의 가중치가 없는 경우에 한하기 때문 배열 사용 map을 ..

2022.07.19