알고리즘/개념1 다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘? - 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘. - 도착 정점 뿐만 아니라 다른 모든 정점까지의 최단 경로도 구할 수 있다. - 간선 가중치가 양수인 경우에만 사용할 수 있다. -> (음수 가중치를 고려해야 하는 경우 벨만-포드, 플로이드-워셜 알고리즘 사용) 수행 과정 1. 시작 정점과 끝 정점 설정. 2. 현재 정점과 연결된 정점 중 방문하지 않았고, 간선 가중치가 가장 작은 정점을 선택. 3. 선택된 정점을 기준으로 간선 비용을 계산하여 최단 거리 테이블에 기록. 4. 2와 3의 과정을 반복하여 끝 정점까지의 비용을 모두 계산 구현 BOJ 1753 최단 경로 1. 각 정점간 방문 및 최단 거리를 확인할 배열을 선언. 2. 연결된 정점 중 간선 가중치가 가장 작은 .. 2023. 9. 16. 이전 1 다음 반응형 LIST
