문상휘파람저장소

플로이드-워셜 알고리즘최단 거리를 구하는 알고리즘입니다.모든 노드 간의 최단 거리를 탐색 - 매우 중요, 출발 노드가 따로 정해진 것이 없습니다. 특징음수 가중치가 있어도 수행할 수 있습니다.동적 계획법의 원리를 사용합니다.O(NNN) - 노드의 세제곱, 꽤 느립니다. 핵심 이론전체의 최단 경로는, 각 부분의 최단 경로가 합쳐져서 만들어집니다.플로이드 워셜 점화식D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])리스트를 선언하고 초기화 해줍니다.최단 거리 리스트에 그래프 데이터를 저장합니다.점화식으로 리스트 업데이트합니다.(3중 for 문) for 경유지 K에 관해(1~N):for 출발 노드 S에 관해(1~N): for 도착 노드 E에 관해(1~N): D[S][E] =..

밸만-포드최단 거리를 구하는 알고리즘입니다. 특징음수 가중치 에지가 있어도 수행할 수 있습니다.전체 그래프에서 음수 사이클의 존재 여부를 파악할 수 있습니다.O(nm) 시간 복잡도 가집니다. 핵심 이론에지 리스트로 그래프를 구현하고 경로 리스트 초기화하기모든 에지를 확인해 정답 리스트 업데이트하기업데이트 반복 횟수 = 노드 수 - 1 음수 사이클이 없을 경우, N-1 에지 사용 횟수를 사용하고 나면, 정답 리스트가 완성된다. 그리고 이렇게 완성된 후, 마지막으로 음수 사이클이 존재하는지 확인한다. 음수 사이클 유무 확인하기모든 에지를 한 번씩 다시 사용해, 업데이트 되는 노드가 발생하는지 확인합니다.업데이트 되는 노드가 있다면, 음수 사이클이 있다는 뜻이 되고, 최단 거리를 찾을 수 없다는 뜻입니다.  ..