최단경로
-
최단경로 문제와 벨만포드 알고리즘 Shortest Path problem && Label correcting AlgorithmDiscrete mathmatics and Problem Solving/10 그래프 2018. 2. 9. 03:25
최단경로 문제와 벨만포드 알고리즘Shortest path Problem && Bellman-ford Algorithm (Label Correcting Algorithm)벨만의 1958년 연구 논문의 서론 부분이다. (RAND corp.) 두 번째 문단에서, " dynamic programming의 (함수 방정식 기법) 사용과 N-1번의 반복후에 수렴하는 반복적 알고리즘이 " 를 보자. 이게 바로 벨만-포드 알고리즘의 큰 핵심이다. Introduction 최단경로를 찾는 문제는 크게 두 종류로 나뉜다. 1 한 점에서 임의의 한 점(다른 모든 점) 까지의 최단경로를 찾는 문제2 모든 점 간의 최단경로를 찾는 문제 이 포스팅은 1번인 한 점에서 임의의 한 점 까지의 최단경로를 찾는 방법(알고리즘)에 대해서 포..