C++을 이용한 최단 경로 검색 과제

소개글

한국항공대 컴공과 데이터 구조시간에 제출한
C++으로 구현한 최단 경로 검색 과제 레포트 입니다.

목차

1.문제 개요
2.분석 및 알고리즘
3.CODE & 주석
4.실행화면
5. 느낀 점

본문내용

1.문제 개요
labeling 알고리즘의 일종으로 Bellman`s eg와 비슷한 원리가 사용됩니다.
프로그램의 순서는 TL 집합에서 가장 작은 원소를 PL로 이동 시키며 이동 시킬때마다 TL집합을 업데이트 해주는 형식을 뜁니다.
TL이 공집합이 되면 검색은 끝나게 됩니다.

2.분석 및 알고리즘
문제 개요에서 설명한 방식을 구현하기위해 버택스의 개수만큼의 버택스 원소를 가지는 배열을 사용하였습니다.
이 배열을 처음 모두 TL 라벨이 붙어있으며 검색해 나감에 따라 점차. PL 라벨로 변화 해가는 형식을 사용하였습니다.

=FixPL 함수=
a.버택스 집합중 TL상태의 원소 중에 가장 작은 원소를 선택합니다.
b.선택된 원소에 라벨을 PL로 변화해준 후 업데이트 함수에 새롭게 PL이된 원소를전달해줍니다.
c.아무 원소도 겁색되지 않는다면(==모두 PL) 검색 이 종료됨니다.

=업데이트 함수=
a.버택스 집합중 TL상태의 원소 중에 전달된 PL 버택스를 거쳐서 가는 경우가 더 짧은 TL이 붙어있는 버택스들의 가중치를 변화시켜줍니다

3.CODE & 주석
#include<iostream>

using std::cout;
using std::cin;
using std::endl;

#define PL 2
#define TL 4



int matrix[6][6]=
{{0,8,10,999,5,999}, //테스트를 위해 미리 입력해놓은 배열
{8,0,2,8,2,6},
{10,2,0,999,6,999},
{999,8,999,0,5,1},
{5,2,6,5,0,2},
{999,6,999,1,2,0}};

class VerTex{ //버택스 클래스
friend class Vertexlist;
int num;
int lengh;
int label;
int routnum;
int rout[6];
};

참고 자료

없음