[공학]bellmanford, 자료구조 및 알고리즘 프로그래밍 보고서

소개글

bellmanford 알고리즘을

c++ class를 이용하여 구현하였습니다.

예제수준의 쉬운 코드입니다.

목차

1. 소스
2. 실행화면
3. 프로그램동작 방법

본문내용

1. 소스
main source file : bellmanford.cpp
header file : bellman.h
class define file : bellman.cpp

★ bellmanford.cpp
#include <stdio.h>
#include <conio.h>
#include \

3. 프로그램동작 방법
프로그램 구성은 node라는 structure와 bellman이라는 class가 존재한다. class 내에서 각각의 edge에대한 weight data를 가지고 있고 node structure형의 배열을 이용하여 각각vertex의 d와 pi를 가지고 있다.
초기화는 0번 vertex를 제외하고 나머지 vertex를 초기화 하는데, d 값과 pi값은 무한대 값으로 초기화를 한다. 그런데 C에서는 무한대가 존재 하지 않으므로 int형의 가장 큰 값을 입력한다. 그리고 배열로 데이터를 관리하기 때문에 pi값은 그 배열의 인덱스이다. 그렇기 때문에 null 값은 존재 하지 않고 무한대를 입력한다.
그리고 실제 알고리즘이 동작하는 부분에서 모든 vertex를 접근하는 부분은 for문을 사용하여 구현하였는데, 한번도 간적이 없는 vertex는 그 값을 비교하여 int_max일 경우 건너 뛰는방식이다. 그렇기 때문에 0번부터 1번, 2번,... 순서대로 진행이 되는데, 1번을 진행하고 있을 때, 3번의 내용이 바뀌면 알고리즘대로라면 다음번 차례에 동작하여야 하지만 2번을 지나고 바로 3번이 진행이 된다. 이것을 방지하기 위해서 미리 백업을 해둔 데이터를 근거로 작업을 진행하게 된다.
사실 이 부분은 크게 상관은 없지만 알고리즘대로 구현하기 위해서 그렇게 했다.
그리고 경로와 거리를 출력하는 부분은 경로를 임의의 배열에 pi를 따라가며 입력을 하고 이것을 거꾸로 꺼내며 출력하는 방식을 이용하였다.

참고 자료

없음