목록최단경로 (2)

생각정리

최단 경로 알고리즘 - 플로이드 워셜 알고리즘 (feat.백준 11404번)

플로이드 워셜 알고리즘의 특징: 모든 지점에서 다른 모든 지점까지의 최단 경로를 구할 수 있음. 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 방식으로 진행됨. 다익스트라 최단 경로 알고리즘은 한지점이 고정이였고, 그 지점으로부터 다른 모든 지점까지의 최단경로를 구하는 알고리즘이였음. 다익스트라 알고리즘은 단계마다 현재까지 최단 거리를 갖는 노드를 하나씩 반복적으로 선택했었다. 그리고 이 노드를 거쳐서 다른 노드로 가는 거리를 구해서, 최단 거리 테이블을 갱신하고 우선순위 큐에 해당 간선들을 추가해서 넣었음. 플로이드 워셜 알고리즘은 매우 단순하다. 매번 방문하지 않은 노드들 중 한가지를 골라서 그 노드를 거쳐가는 최단 경로와 지금까지 구한 최단 경로를 비교해서 테이블을 갱신시킴. Dab가 a에서 b로 가..
코딩테스트_알고리즘_공부 2022. 11. 5. 21:06
최단 경로 알고리즘 - 다익스트라(=데이크스트라) (feat.백준 1753번)

다익스트라 최단경로 알고리즘은 특정 노드에서 출발해서 다른 노드로 가는 각각의 최단 경로를 모두 구할 수 있는 알고리즘이다. (다만, 이번 글에서는 최단 경로의 거리만 구할 수 있는 알고리즘을 공부한다. 추후에 경로까지 구하는 알고리즘을 업데이트 하도록 하겠습니다) 다익스트라 알고리즘의 조건) 방향/무방향 그래프 모두에서 사용할 수 있으며, 간선 간에 음의 간선이 없어야 함. 음의 간선이 문제에서 주어질 일은 거의 없기 때문에 크게 신경쓰지 않아도 되는 조건임. 실제로 다익스트라 알고리즘은 현실 세계의 gps sw의 기본 알고리즘으로 쓰인다고 한다. 다익스트라 최단 경로 알고리즘의 분류: 그리디 알고리즘으로 분류됨. 즉, 매 순간에 최선(가장 비용이 적은 간선으로 갈 수 있는 노드)의 선택을 하기 때문이..
코딩테스트_알고리즘_공부 2022. 11. 5. 20:15
이전 Prev 1 Next 다음