소개글
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
압축파일 내 파일목록
GObject.h
Graph.cpp
Graph.dsp
Graph.vcproj
input1.txt
input.txt
StdAfx.cpp
StdAfx.h
graph.doc
GEObject.cpp
GEObject.h
GObject.cpp
참고 자료
없음