"데이크스트라 알고리즘"의 두 판 사이의 차이

잔글
잔글 (봇: 틀 이름 및 스타일 정리)
데이크스트라 알고리즘과는 달리, [[벨먼-포드 알고리즘]]은 소스 꼭짓점 ''s''에서 도달할 수 있는 [[음수 사이클]]이 없으면 음수 가중치가 있을 때에도 사용할 수 있다. 이런 사이클이 존재하면, 이 사이클에 들어가서 한 바퀴를 돌 때 마다 전체 비용이 감소하기 때문에 최단 경로가 없다. 데이크스트라 알고리즘에 (음수 변을 제거하고 음수 사이클을 감지하기 위해)벨먼-포드 알고리즘을 결합해서 음수 가중치를 다룰 수 있으며, 이런 알고리즘은 [[존슨 알고리즘]]이라고 불린다.
 
[[A* 알고리즘]]은 데이크스트라 알고리즘을 일반화 한 것으로, 목적지까지의 "거리"의 하한에 관한 정보를 얻을 수 있을 때 탐색해야 할 부분 그래프의 크기를 줄일 수 있다. 이 접근은 [[선형 계획법]]의 관점에서 볼 수 있다: there is a natural [[최단 경로 문제#선형 계획법 공식|최단 경로의 계산에서 선형 계획법]]이 있고, 그 [[쌍대성 (최적화)|쌍대 선형 계획법]]의 해법이 실행 가능하다는 것은 [[일관 휴리스틱]]을 형성한다는 것이다(대략적으로 말하면, 서명 관례가 문헌마다 다르기 때문이다). 이 실행 가능한 쌍대 / 일관 휴리스틱은 음이 아닌 [[감소 비용]]을 정의하고 A*은 본질저그로 이 감소 비용을 가지고 데이크스트라 알고리즘을 돌리는 것이다. 쌍대 선형 계획법이 약한 [[허용적 휴리스틱|허용성]] 조건을 만족하면, A*는 벨먼-포드 알고리즘에 더 비슷하다.
 
데이크스트라 알고리즘의 기초가 되는 과정은 [[프림 알고리즘]]에서 사용되는 [[탐욕 알고리즘|탐욕]] 과정과 유사하다. 프림 알고리즘의 목적은 그래프에 있는 모든 꼭짓점을 연결하는 [[최소 신장 트리]]를 찾는 것이나, 데이크스트라 알고리즘은 꼭짓점 두 개 만을 고려하는 것이다. 프림 알고리즘은 시작 꼭짓점의 전체 가중치로 평가하지 않고 각각의 가중치만을 평가한다.