[자료구조 자료구조] Floyd 알고리즘(shortest path algorithm;최단경로)

소개글

최단 경로 알고리즘(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

참고 자료

없음