1. 벨만-포드 알고리즘 개요 그래프에서 최단 거리를 구하는 알고리즘. 다익스트라 알고리즘과 달리 에지의 가중치가 음수여도 사용할 수 있으며, 이로 인해 음수 사이클 존재 여부 확인 문제에서 많이 사용 다익스트라 알고리즘의 시간복잡도(O(ElogV))에 비해 표에 보이는 것과 같이 노드가 그대로 곱해지므로 음수 가중치 에지가 있거나 음수 사이클의 존재 여부를 판단할 때 사용하는 것이 좋음. 구현 방법 특징: 그래프를 에지 번호에 따라 출발 노드, 종료 노드, 가중치로 이루어진 에지 리스트로 구현함. 에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화 최단 경로 리스트의 경우 출발 노드를 0, 나머지 노드를 무한대로 초기화 정답 리스트 업데이트하기 모든 에지를 확인해 sp[src_node]가 무한이 ..