소개글

C++을 사용하여, all-pair shortest path를 구현했습니다. 기법으로는 repeated squaring, Floyd-Warshall, Johnson's algorithm을 사용했으며, 각각의 기법에 대한 source code 및 report를 첨부합니다.
report는 각 기법에 대한 분석 및 결과에 대한 고찰을 다루고 있으며, source code는 C++을 공부하시는 분이라면 크게 도움될 것이라 생각합니다.
또한 알고리즘을 공부하시는 분이라면 이 소스 및 report가 크게 도움이 되실 것입니다.
(adjacency matrix를 사용하였으며, #은 infinite value를 의미합니다.)

컴파일 실행환경

vc++ (6.0, .Net) /
windows 기반

본문내용

#ifndef __GEOBJECT_H__
#define __GEOBJECT_H__

class GGraph;
class GMatrix;

//===============================
// Graph Executor Class
//===============================
class GraphExecutor
{
public:
GraphExecutor();
~GraphExecutor();

void Initialize();
//Input File에서 Data읽어오기
void SetData(LPCSTR lpszInputFileName);
//Main Function
int Run();
protected:
//각 algorithm을 수행
void DoRepeatedSquare();
void DoFloydWarshall();
void DoJohnson();
protected:
//Sub routines
void _DoDijkstra(GGraph* pGraph,int i);
bool _DoBellmanFord(GGraph* pGraph,int i);
protected:
GGraph* m_pInputGraph;
GMatrix* m_matResult;

FILE* m_pOutput;
};

#endif

압축파일 내 파일목록

참고 자료

없음