자료구조_알고리즘/Algorithm
[Algorithm/Java] 벨만-포드 알고리즘 (최단거리, 음수 가중치 그래프)
벨만-포드(bellman-ford-moore) 알고리즘벨만 - 포드 알고리즘은 그래프에서 음수 가중치를 가진 간선이 있을 때 최단거리를 구하는 알고리즘이다.다익스트라 알고리즘과 같이 특정 노드에서 다른 모든 노드까지의 최단 거리를 탐색한다.다익스트라 알고리즘과 다르게 음수 간선이 포함되어 있어도 최단 경로를 구할 수 있다.음수 사이클이 있을 경우 정상 동작하지 않는다.음수 사이클의 존재 여부를 파악할 수 있다.매번 모든 간선을 확인하기 때문에 다익스트라에 비해 느리다.시간복잡도 : O(VE) => Vertex * Edge벨만 - 포드 알고리즘 동작 원리1. Edge 리스트로 그래프를 구현하고 최단경로 배열 초기화 하기위에서 말했듯이 벨만 - 포드 알고리즘은 매번 모든 간선을 확인한다.따라서 Edge 클래..
