[JS] 다익스트라 알고리즘

1. 다익스트라 알고리즘 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단거리 알고리즘이다. 최단거리 알고리즘의 사용 예시로 도시의 지도에서 출발지에서 목적지 사이의 거리 중 가장 짧은 거리를 찾는 네비게이션이나, 인공위성 GPS 소프트웨어 등이 있다. 다익스트라 알고리즘은 음의 간선을 포함할 수 없기 때문에 모든 가중치가 양수여야만 한다 다익스트라 알고리즘의 실행 순서는 다음과 같이 동작한다. 모든 꼭지점을 미방문 상태로 만든다. 시작 정점을 정한다(정점 A에서 탐색을 시작할 건지, 정점 B에서 시작할 건지 결정). 시작정점 A를 방문상태로 처리한다(시작 정점을 A라고 가정). 정점 A에 인접한 정점으로 가는 모든 거리 값을 기록한다. 정점 A에 각각의 인접 정점과 연결된 거리 중에서, ..

2020.07.02