플로이드 - 워셜(floyd - warshall) 알고리즘 플로이드 - 워셜 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다. 시작점을 정해놓고, 해당 시작점에서 다른 모든 노드로의 최단거리를 구하는 다익스트라, 벨만-포드 알고리즘과 다르게 각각의 모든 노드에 대하여 다른 모든 노드로의 최단거리를 구할 수 있는 알고리즘이다. 모든 노드 간에 최단 경로를 탐색할 수 있다. 음수 가중치 간선이 있어도 수행할 수 있다. 동적 계획법을 이용하여 코드가 비교적 간단하다. 다른 알고리즘과 다르게 모든 노드사이의 최단거리를 도출하는 알고리즘이기 때문에 3중 for문을 이용한다. 시간 복잡도는 O( N^ 3)이다. 플로이드 - 워셜 알고리즘 동작 원리 1. 핵심 이론 2차원 배열에 모든 노드에 대하여 다른 모든 ..
벨만-포드(bellman-ford-moore) 알고리즘벨만 - 포드 알고리즘은 그래프에서 음수 가중치를 가진 간선이 있을 때 최단거리를 구하는 알고리즘이다.다익스트라 알고리즘과 같이 특정 노드에서 다른 모든 노드까지의 최단 거리를 탐색한다.다익스트라 알고리즘과 다르게 음수 간선이 포함되어 있어도 최단 경로를 구할 수 있다.음수 사이클이 있을 경우 정상 동작하지 않는다.음수 사이클의 존재 여부를 파악할 수 있다.매번 모든 간선을 확인하기 때문에 다익스트라에 비해 느리다.시간복잡도 : O(VE) => Vertex * Edge벨만 - 포드 알고리즘 동작 원리1. Edge 리스트로 그래프를 구현하고 최단경로 배열 초기화 하기위에서 말했듯이 벨만 - 포드 알고리즘은 매번 모든 간선을 확인한다.따라서 Edge 클래..
다익스트라(dijkstra) 알고리즘 다익스트라 알고리즘은 그래프에서 최단거리를 구하는 알고리즘이다. 가중치 그래프 상에서 출발노드에서 목표노드까지 이동하는 가장 짧은 경로를 찾는 방법을 찾는다. 하나의 출발 노드에서 다른 모든 노드로의 최단 경로를 구할 수 있다. 에지(간선)은 모두 양수여야 한다. 시간 복잡도 : O(ElogV) 그리디와 DP의 특성을 갖고 있다. 다익스트라 알고리즘 동작 원리 1. 인접 리스트로 그래프를 구현한다. [1] ->[ 2, 8 ] 은 1에서 2로 가는 가중치가 8이라는 뜻이다. 실제로는 아래와 같이 Edge 클래스를 만들어서 Edge 형 ArrayList배열을 선언하여 구성하였다. ArrayList[] graph; class Node{ int to; //가리키는 노드 in..
