2021.07.04
존슨 알고리즘(Johnson's Algorithm)
존슨 알고리즘(Johnson's Algorithm) 벨만-포드 알고리즘 과 다익스트라 알고리즘 의 방법을 결합하여 모든 정점 사이의 최단 경로를 구하는 알고리즘 다익스트라 알고리즘의 효율성을 활용함과 동시에 음수 가중치를 갖는 그래프에 대해서도 올바른 결과를 생성할 수 있음. 상당히 새로운 접근 방법을 사용함. 음수 가중치에 대한 다익스트라 알고리즘의 한계를 극복하기 위해 전체 에지 가중치를 음수가 아닌 형태로 변환 함. 벨만-포드 알고리즘 과 적절한 수학 논리 를 결합하여 이루어짐. 동작 방식 그래프에 새로운 더미(Dummy) 정점 을 추가함. 그리고 이 더미 정점과 나머지 모든 정점 사이에 가중치가 0인 에지를 연결함. 이후 벨만-포드 알고리즘 을 이용하여 더미 정점과 나머지 정점들 사이의 최단 경로..
