반응형 파이썬 최단 경로1 [Python][이코테] 최단경로 / 다익스트라 알고리즘(1) 컴퓨터공학과 학부 수준에서 주로 사용할 수 있는 최단 경로 알고리즘은 3가지가 있다. 다익스트라 알고리즘 플로이드 워셜 벨만 포드 이중 다익스트라 알고리즘에 대해서 2번에 걸쳐 공부해보도록 한다. 참고로 최단경로 알고리즘은 앞서 배운 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 그대로 적용된다. 다익스트라 알고리즘 다익스트라 알고리즘은 그래프에서 여러 노드가 있고, 특정 노드에서 다른 노드로 가는 최단 경로를 구하는 알고리즘이다. 음의 간선이 없어야 하며, 실제 지도앱에서 길 찾기를 사용할 때 쓰이는 알고리즘이다. 방법은 다음과 같다. 출발 노드를 정한다. 최단 거리 테이블을 초기화 한다. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 해당 노드를 거쳐 다른 노드로 가는 비용을 .. 2022. 11. 9. 이전 1 다음 반응형
