728x90 다익스트라1 Dijkstra 알고리즘 목적 다익스트라 알고리즘을 이해하기 다익스트라 알고리즘을 Java로 구현하기 시작하는 말 티스토리 블로그로 이전하고 처음 포스팅하는 글입니다. 첫 게시글은 전 github.io 블로그에서 가장 클릭 수가 많았던 다익스트라 알고리즘을 옮기려고 한다. (검색어는 '다익스트라 2차원 배열') 다익스트라(dijkstra) 알고리즘 이란? 다익스트라 알고리즘은 최단경로를 탐색하는 알고리즘이다. 구현 방법으로 2차원 배열 또는 힙(Heap)을 이용하여 구현할 수 있으며 각각 O(N^2)와 O(ElogN) 시간복잡도를 가진다. 다익스트라 알고리즘은 음수 가중치를 가진 그래프에서는 사용할 수 없는 단점이 있는데 이때에는 벨만-포드 알고리즘을 사용해야 합니다. 원리 1. 모든 가중치를 무한으로 설정한다. 2. 방문하지 .. 2021. 6. 22. 이전 1 다음 728x90