데이크스트라 알고리즘(Dijkstra algorithm)은 네덜란드의 컴퓨터과학자 에츠허르 데이크스트라의 이름을 딴 알고리즘이다. 데이크스트라의 이름을 오독한 다익스트라 알고리즘이라는 표기 또한 존재한다. 이 알고리즘은 어떤 간선도 음수 값을 갖지 않는 방향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 풀기 위한 것으로, 예컨대 그래프의 점들이 각각 도시를 나타내고, 연결선들이 도시 사이를 연결하는 도로의 길이를 나타낸다면, 데이크스트라 알고리즘을 통하여 두 도시 사이의 최단 경로를 찾을 수 있다. 출처 위키백과
//입력 데이터
8 //노드의 수
0,2,-1,-1,-1,3,-1,-1 //1번 노드의 초기값
2,0,1,4,-1,-1,-1,-1 //2번 노드의 초기값
-1,1,0,-1,3,-1,-1,-1 //3번 노드의 초기값
-1,4,-1,0,3,-1,2,-1 //4번 노드의 초기값
-1,-1,3,3,0,-1,-1,4 //5번 노드의 초기값
3,-1,-1,-1,-1,0,6,-1 //6번 노드의 초기값
-1,-1,-1,2,-1,6,0,4 //7번 노드의 초기값
-1,-1,-1,-1,4,-1,4,0 //8번 노드의 초기값
설명) 0,2,-1,-1,-1,3,-1,-1 //1번 노드의 초기값 경우
1번 노드에서 1번 노드까지의 cost가 0(자기 자신)
1번 노드에서 2번 노드까지의 cost가 2(연결됨)
1번 노드에서 3번 노드까지의 cost가 -1(직접 연결되어 있지 않음)
1번 노드에서 4번 노드까지의 cost가 -1
1번 노드에서 5번 노드까지의 cost가 -1
1번 노드에서 6번 노드까지의 cost가 3(연결됨)
1번 노드에서 7번 노드까지의 cost가 -1
1번 노드에서 8번 노드까지의 cost가 -1
즉 아래의 트리처럼 표현할 수 있음.
입력 데이터를 통해 각 노드별로 최단 거리를 dijkstra 알고리즘을 이용하여 라우팅 테이블을 구하는 프로그램을 작성, 링크리스트,OSPF
|
input.txt |
|
8
0 2 -1 -1 -1 3 -1 -1
2 0 1 4 -1 -1 -1 -1
-1 1 0 -1 3 -1 -1 -1
-1 4 -1 0 3 -1 2 -1
-1 -1 3 3 0 -1 -1 4
3 -1 -1 -1 -1 0 6 -1
-1 -1 -1 2 -1 6 0 4
-1 -1 -1 -1 4 -1 4 0 |
|
Main.c |
|
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode{
int nodename;
int cost;
struct ListNode *link;
}ListNode;
//<-- 단순링크리스트 -->
//phead: 리스트의 헤드 포인터와 포인터
//p: 선행 노드
//new_node : 삽입될 노드
void insert_node(ListNode **phead, ListNode *p, ListNode * new_node);
void remove_node(ListNode **phead, ListNode *removed);
void display_node(ListNode *head);
ListNode *search_node(ListNode *head,int nodename);
ListNode *create_node(int nodename, int cost, ListNode *link);
ListNode *minsearch_node(ListNode *head);//리스트중 최단경로검색
void change_node();//최단거리 알고리즘 반복부분
void display_table(int MyNum);//라우팅테이블 표시
void init();//초기화
ListNode *per_list=NULL;//영구 노드 리스트
ListNode *temp_list=NULL; //임시 노드 리스트
ListNode *tempnode=NULL;//임시 노드
int nodesu;//노드의 수
int data[50][50];//네트워크 인접 행렬
int nextnode[50];//영구 리스트에 사용된노드의 Next라우터
int main(void){
FILE *in;
char input=NULL;
int i,j;
in=fopen("input.txt","r");
if(in ==NULL){
printf("File Not Found\n");
return 0;
}
printf("파일열기성공\n");
fscanf(in,"%d",&nodesu);
printf("노드의 수 : %d\n",nodesu);
for( i = 1 ; i<=nodesu ; i++){
for( j = 1 ; j<=nodesu ; j++){
fscanf(in,"%d",&data[i][j]);
printf("%d ",data[i][j]);
}
printf("\n");
}
fclose(in);
//첫번째 노드에서의 최단경로 라우팅테이블
for( i = 1 ; i<=nodesu ; i++){
insert_node(&temp_list,NULL,create_node(i,data[i][i],NULL));
nextnode[i]=i;
while(temp_list !=NULL){
change_node();
}
display_table(i);
init();
}
return 0;
}
void insert_node(ListNode **phead, ListNode *p, ListNode * new_node)
{
if( *phead == NULL){//공백리스트인 경우
new_node->link = NULL;
*phead = new_node;
}else if( p==NULL ){//p가 NULL이면 마지막 노드로 삽입
p=*phead;
while(p->link!=NULL){
p = p->link;
}
p->link=new_node;
new_node->link=NULL;
}else{ //p 다음에 삽입
new_node->link= p->link;
p->link = new_node;
}
}
void remove_node(ListNode **phead, ListNode *removed){
ListNode * p=*phead;
if( p == removed){
*phead = (*phead)->link;
// printf("삭제탐색 성공\n");
return;
}
while( p!=NULL){
if( p->link ==removed) {//탐색 성공
p->link = removed->link;
// printf("삭제탐색 성공\n");
return;
}
p = p->link;
}
//printf("탐색 실패\n");
//free(removed);
}
void display_node(ListNode *head){
ListNode *p=head;
while(p!=NULL){
//printf("%d(%d)->", p->nodename,p->cost);
p = p->link;
}
//printf("\n");
}
ListNode *search_node(ListNode *head,int nodename){
ListNode *p;
ListNode *findnode=NULL;
p = head;
//printf("탐색 시작\n");
while( p!=NULL){
//printf("p->%d nodename->%d \n",p->nodename,nodename);
if( p->nodename ==nodename) {
findnode = p;
// printf("탐색 성공\n");
return findnode;//탐색 성공
}
p = p->link;
}
// printf("탐색 실패\n");
return NULL;//탐색 실패시 NULL반환
}
ListNode *minsearch_node(ListNode *head){
ListNode *p=head;
ListNode *minnode=NULL;//최단경로 노드
if( p!=NULL){
minnode = p;
}
while( p!=NULL){
if(minnode->cost > p->cost){
minnode=p;
}
p = p->link;
}
return minnode;
}
ListNode *create_node(int nodename, int cost, ListNode *link)
{
ListNode *new_node;
new_node = (ListNode*)malloc(sizeof(ListNode));
if( new_node == NULL ) printf("malloc error");
new_node->nodename=nodename;
new_node->cost=cost;
new_node->link = link;
return (new_node);
}
void change_node(){
int i;
ListNode *findnode;//searchnode함수로 찾은노드
//임시 노드 리스트중 비용이 가장 작은 노드
tempnode = minsearch_node(temp_list);
//임시 노드 리스트에서 제거
remove_node(&temp_list,tempnode);
//영구 노드 리스트로 옮기기
insert_node(&per_list,NULL,tempnode);
//printf("현재 임시->영구 %d(%d)\n",tempnode->nodename,tempnode->cost);
//tempnode리스트에 이웃 추가(중복은 제거)
for( i = 1 ; i <=nodesu ; i++){
if( search_node(per_list,i) ==NULL){//영구리스트에 있는 노드인지 확인
if(data[tempnode->nodename][i] != -1 && data[tempnode->nodename][i] != 0){//인접 노드만 추가
//만약 임시 리스트에 존재한다면 비교후 작은비용으로 변경
if((findnode=search_node(temp_list,i)) !=NULL)
{
//printf("임시리스트에서 찾은 %d(%d)\n",findnode->nodename,findnode->cost);
if( tempnode->cost+data[tempnode->nodename][i] < findnode->cost){
nextnode[i]=tempnode->nodename;//이전라우터경로수정
findnode->cost=tempnode->cost+data[tempnode->nodename][i];
//printf("작은비용으로 변경%d\n",findnode->cost);
}else{
//printf("원래있던 비용이 더싸다.\n");
}
display_node(per_list);
display_node(temp_list);
}else{//임시 리스트에 없는경우 노드 추가
//printf("%d 는 임시리스트에 추가\n",i);
//이전 라우터위치 기억
nextnode[i]=tempnode->nodename;
insert_node(&temp_list,NULL,create_node(i,data[tempnode->nodename][i]+tempnode->cost,NULL));
display_node(per_list);
display_node(temp_list);
}
}
}else{
//printf("%d 는 영구리스트에 이미 존재\n",i);
}
}
//printf("한바퀴 \n");
}
void display_table(int MyNum){
ListNode *p;
int i,temp=0,pre;;
printf("\n <%d 번 라우팅 테이블> \n",MyNum);
printf(" Node Cost Next Router \n");
for( i = 1 ; i<=nodesu ; i++){
p=search_node(per_list,i);
if(MyNum == nextnode[i]){
printf(" %2d %2d -\n", i,p->cost);
}else{
//라우팅 역추적 경로찾기실행
temp=nextnode[i];
while(MyNum != temp){
pre=temp;
temp=nextnode[temp];
}
printf(" %2d %2d %2d\n",i,p->cost,pre);
}
}
printf("\n");
}
void init(){
int i;
per_list=NULL;//영구 노드 리스트
temp_list=NULL; //임시 노드 리스트
tempnode=NULL;//임시 노드
for(i=0; i<=nodesu ; i++){
nextnode[i]=0;
}
} |
