최단거리 최소환승 알고리즘 구현(지하철노선도)

소개글

최단거리 최소환승 알고리즘 구현(지하철노선도)에 대한 보고서 자료입니다.

목차

1) ds_hw5.cpp: 메인함수를 포함하고, 파일처리 및 그래프 생성
#include "graph.h"
#include "dijkstraAlg.h"
void readFile(char *file_name, char (*temp)[100]) //read a file input
void makeGraph(char (*temp)[100]){ //add graph nodes
int getStation(char id[]){ //get station's id and return its no
int main(void)

2) graph.h: 인접리스트로 구현되고, 기타 세부 함수들을 포함
//graph by adjecency list
#define NUM_STATIONS 400 // max number of stations
#define NOT_CONNECTED 7777777 // for dijkstra algorithm
typedef struct gNode
{
int no; // station number
int time; // time-cost
char id[14]; //station id
int transferable; // is a station transferable or not?
struct gNode *link;
} gNode;
/* global variables */
gNode* gHeader[NUM_STATIONS]={NULL}; //header array pointing gNodes
int visited[NUM_STATIONS]; //for depth first search
int distance[NUM_STATIONS]; // shortest distance from start
int path[NUM_STATIONS]; // shortcut path
int found[NUM_STATIONS]; // visited path

void addGNode(int no1, int no2, int a_time, char* a_id1, char* a_id2) //add graph node
int idToNo(char id[]) //change id into no and return no.
char* noToId(int a_no, char a_id[]){ // return no's id
int timeCost(int v1, int v2){ //time-cost between v1 and v2
int timeCost2(int v1, int v2){ //time-cost between v1 and v2
void initGV(){ //initializing global variable

3) dijkstraAlg.h : 최단시간, 최소환승 경로를 찾는데 이용된 dijkstra algorithm 구현
void printDistance()
int choose(int distance[], int n, int found[])
void findShortestPath(int start, gNode* gHeader[], int distance[], int n, int found[]) //by dijkstra's algorithm( n=NUM_STATIONS)
void findMinTransPath(int start, gNode* gHeader[], int distance[], int n, int found[]) //by dijkstra's algorithm( n=NUM_STATIONS)
int displayPath(int start, int end) //return the number of stations

본문내용

보고서 내용 일부 발췌

1) 파일처리 및 그래프 생성
기본적인 파일 포인터와 함수를 이용하여 파일을 읽어오도록 하였습니다. fgets함수를 이용해 라인별로 읽어와 배열로 저장하도록 하였습니다. 그리고 그 배열을 가지고 strtok함수를 이용해 공백 단위로 끊어 토큰을 만들고 이를 다섯개 단위로 저장하여 인접리스트로 구현된 그래프에 노드를 추가하는 함수를 호출할 수 있도록 구현하였습니다.
또한 그래프 생성시에는 파일의 다섯 필드를 모두 인자로 받아 linked list의 노드로 추가할 수 있도록 하였으며, 이에 덧붙여 환승역인지 여부를 strcmp로 이름을 비교하여 삽입하도록 하였습니다.

2) 최단거리 경로 찾기
인접리스트로 구현된 그래프를 바탕으로, 시작노드로부터 최단거리 추적이 가능한 dijkstra algorithm을 이용하여 최단거리 경로를 찾도록 하고 소요시간도 구할 수 있도록 구현하였습니다. 경로는 간단한 배열을 이용한 스택을 통해 올바른 순서대로 경로를 출력할 수 있도록 하였고, 소요 시간 계산은 알고리즘에 의해 계산된 distance값을 이용하여 구할 수 있었습니다.

3) 최소환승 경로 찾기
.............

키워드

C,   프로그래밍,   최단거리,   최소환승,   알고리즘,   지하철,   노선도