알고리즘 (3) 썸네일형 리스트형 벨만 포드 알고리즘(Bellman Ford Alogorithm) 벨만 포드 알고리즘(Bellman Ford Alogorithm) 벨만 포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 최단 경로 알고리즘이다. 탐색을 하는 방식도 다익스트라와 유사하다. 다익스트라 알고리즘과의 차이점은 벨만 포드 알고리즘 다익스트라 알고리즘 음의 가중치가 간선에 있을때도 작동하며 음의 사이클도 감지함 음의 가중치가 간선에 있을경우 작동하지 않음 상대적으로 시간이 더 소요됨 벨만 포드의 알고리즘보다 시간이 덜 소요됨 시간복잡도는 O(VE) 시간복잡도는 O(ElogV) [작동방식] 1. 출발 노드를 설정한다 2. 최단 거리 배열을 초기화한다. 3. 인접한 노드로 가는 간선을 탐색후 최단거리 배열을 갱신한다. 4. 3번과정을 (V-1)번 반복한다. 5. 음수 사이클의 존재 유무를 판별하려면 한.. 다익스트라 알고리즘(Dijkstra's algorithm) - 우선순위 큐 다익스트라 알고리즘(Dijkstra's algorithm) - 우선순위 큐 우선순위 큐 구현에는 전 게시물에서 사용한 인정 행렬 구현을 수정해 사용한다. https://stdio-han.tistory.com/85 다익스트라 알고리즘(Dijkstra's algorithm) - 인접 행렬 다익스트라 알고리즘(Dijkstra's algorithm) 다익스트라 혹은 데이크스트라 알고리즘 이라고부르는 이것은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단경로를 찾는 알고리 stdio-han.tistory.com [설명] 이전에 사용한 인접행렬 방식과 다른 부분을 위주로 설명한다. // (a,b) -> a[0] - b[0] 오름차순 정렬 PriorityQueue pq = new Priority.. 다익스트라 알고리즘(Dijkstra's algorithm) - 인접 행렬 다익스트라 알고리즘(Dijkstra's algorithm) 다익스트라 혹은 데이크스트라 알고리즘 이라고부르는 이것은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단경로를 찾는 알고리즘이다. 일반적인 다익스트라 알고리즘문제로는 한 꼭짓점을 "소스" 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘으로 최단 경로 트리를 만드는것이다. 그래프의 간선마다 가중치가 존재하고, 음의 가중치는 존재하지 않는다. 음의 가중치가 존재한다면 다익스트라를 사용할 수 없다. 구현하는 방법에는 인접행렬방식과 우선순위 큐 두가지가 있다. 먼저 다익스트라를 이해하기 위해 인정행렬이 더 간단하기 때문에 먼저 알아보자. 동작 과정을 간단하게 설명하자면 다음과 같다. 1. 출발 노드를 설.. 이전 1 다음
