[자료구조] BellmanFord 알고리즘

소개

책참고 해서 직접 작성한 C++ 프로그램입니다...^^ 즐공

목차

1. 문제 내용및 설명
2. 알고리즘
3. 소스설명
4. 결과화면
5. 느낀점

본문내용

1. 문제 내용 및 설명BellmanFord 알고리즘을 이용하여 단일 시발점에서 모든 종착점으로의 최단경로와 최소 가중치를 구하라.
§ 그래프는 인접행렬로 구현한다.
§ 길이 인접 행렬을 입력 받는다.
§ 최단경로와 최소 가중치를 출력한다.
2. 알고리즘
§ 음의 길이 사이클이 존재하지 않을 때 n개의 정점으로된 그래프에서 최대 n-1개의 간선으로 된 임의의 두 정점 사이의 최단 경로는 존재한다.
§ 모든 u에 대해 dist^n-1[u]를 구할 때
(1) 최대 k(k>1)개의 간선을 가질 수 있는 상황에서 v로부터 u까지의 최단 경로가 k-1개 이하의 간선을 갖는다면, dist^k[u]=dist^k-1[u]이다.
(2) 최대 k(k-1)개의 간선을 가질수 있는 상황에서 v로부터 u까지의 최단 경로가 정확히 k개의 간선을 갖는다면, 이 경로는 v에서 어떤 정점 j로의 최단 경로와 간선<j,u>로 구성된다. V에서 j로의 최단경로는 k-1개의 간선을 포함하고 그 길이는 dist^k-1[j]가 된다.여기서 그래프에 있는 간선<I,u>에 속하는 모든 정점 I는 j의 후보가 된다. 최단 경로를 구하는 관점에서 보면, dist^k-1[I]+length[I][u]의 값을 최소화시키는 I가 j로 되어야 한다.
§ dist를 다음과 같은 반복식으로 표현한다.

참고자료

· C++ 자료구조론