[자료구조 자료구조] Floyd 알고리즘(shortest path algorithm;최단경로)
- 최초 등록일
- 2004.06.25
- 최종 저작일
- 2004.06
- 7페이지/ 압축파일
- 가격 1,000원
소개글
최단 경로 알고리즘(floyd 알고리즘)을 이용하는 소스입니다.
========= 과제 요청 사항 =========
노드 개수를 입력으로 받아서, Connected Random Graph 를 만들고,
임의의 두 개의 노드를 입력받으면, 최단 경로를 출력한다.(노드 개수: 10, 100, 1000, 10000 개까지 검사)
컴파일 실행환경
총 7파일
floyd.c
Floyd.dsp
Floyd.dsw
Floyd.exe
Floyd.ncb
Floyd.opt
Floyd.plg
본문내용
============ 소스 일부 내용 ===============
void createMatrix(int cost[][MAX_VERTICES]);
void printMatrix(int matrix[][MAX_VERTICES]);
void allcosts(int cost[][MAX_VERTICES], int distance[][MAX_VERTICES], int path[][MAX_VERTICES]);
void pathPrint(int path[][MAX_VERTICES], int distance[][MAX_VERTICES], int v1, int v2);
void pathing(int path[][MAX_VERTICES], int v1, int v2);
int showMenu(int path[][MAX_VERTICES], int distance[][MAX_VERTICES]);
void finalizingGraph(int cost[][MAX_VERTICES]);
int doesConnect(int cost[][MAX_VERTICES], int *notVisited);
void dfs(int cost[][MAX_VERTICES], int v);
short int visited[MAX_VERTICES]; // 방문한 노드인가를 체크하기 위한 배열
void main() {
int cost[MAX_VERTICES][MAX_VERTICES]; // 초기 비용 배열
int distance[MAX_VERTICES][MAX_VERTICES]; // 최단 경로 비용 배열
int path[MAX_VERTICES][MAX_VERTICES]; // 최단 경로 배열
srand((unsigned)time(NULL));
// 입력
createMatrix(cost); // matrix 생성
finalizingGraph(cost); // connected 되었는지 확인하고
// connected 되지 않았다면 edge를 추가한다.
// 초기 비용 인쇄
printf("=============== Original Cost ===============");
printMatrix(cost);
// floyd's 알고리즘 적용
allcosts(cost, distance, path);
// 최단 경로 비용 인쇄
printf("\n\n============= ShortestPath Cost =============");
printMatrix(distance);
// 메뉴 출력
while(showMenu(path, distance)) ;
printf("\n ---------------------------- End ---------------------------- \n");
}
압축파일 내 파일목록
floyd.c
Floyd.dsp
Floyd.dsw
Floyd.exe
Floyd.ncb
Floyd.opt
Floyd.plg
참고 자료
없음