사실상 for문 하나짜리 과제였는데

자료구조는 대략 연결리스트를 포함한 배열로 정의


run_dijkstra 에 출발지 넣으면 

모든 정점에서 출발지와의 최소거리가 나옴 경유한 노드도 기록하니 최단거리 ㄳㄳ

과제로 냈던 거고 최소힙은 쓰지말래


뭐.. for문 제어 조건을 추가하자면 이전까지의 최소경로가

계속  mindist(); 로 잡히면 2중 for문 끝내면 될듯


스탠포드 CS 과정에서 따온 과제일껄?


문자열 처리는 함수찾고 하기 귀찮아서 배열 두개로 쓱쓱 { } 안에서 split 같은거 만들어서 표준입출력으로 대충 끼워맞춤 


난 사실 이거 수업을 못들어서 그냥 후배한테 과제 내용 알려달래서 쓱쓱짬 소요시간은 2시간 정도 





#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <time.h>


#define __func__  __FUNCTION__

#define MAX_DISTANCE    1000000     // if no path exists

#define MAX_NUM_NODES   200         // 200 vertices labeled 1 to 200

#define MAX_VERTEX_ID   200         // 200 vertices labeled 1 to 200


double stime, etime;


struct vertex {

   int             id;             // node id

   unsigned int    dist;           // minimum distance to source

   int            f;            

   int            on;

   struct edge *ptr;


};

struct vertex *m_varray[MAX_NUM_NODES]; // array of all vertices


struct edge {

   int toid;

   int w;

   struct edge *ptr;

};


int m_n = 0; // total number of i->j edges. 

int m_e = 0; // 'm_e/2' is the actual number of undirected edges 

struct vertex* find_vertex (unsigned int id);

struct vertex* add_vertex (unsigned int id);

struct edge* add_edge (unsigned int fromid, unsigned int toid,  unsigned int ecost);

struct vertex* mindist();

void run_dijkstra(int start_point);

int read_input_file(char *filename);


int main (int argc, char *argv[]) {


char *filename = "dijkstraData.txt";


   /* read input file from filename */

   read_input_file(filename); 

   

   stime = clock();


   ///* run dijkstra here */

   run_dijkstra(1);


   etime = clock();


   printf("homework output: ");

   printf("shortest distance to vertices 7,37,59,82,99,115,133,165,188,197 ");

   printf("%d,%d,%d,%d,%d,%d,%d,%d,%d,%d ",

      m_varray[7-1]->dist, m_varray[37-1]->dist,

      m_varray[59-1]->dist, m_varray[82-1]->dist,

      m_varray[99-1]->dist, m_varray[115-1]->dist,

      m_varray[133-1]->dist, m_varray[165-1]->dist,

      m_varray[188-1]->dist, m_varray[197-1]->dist);


   /* calculate running time */

   printf("run time : %f " ,(etime - stime) /  CLOCKS_PER_SEC);


   return 0;

}



// run Dijkstra algorithm

void run_dijkstra(int start_point) {

   int i;


   int index = start_point-1;


   //init start point 

   struct edge *find =   m_varray[index]->ptr;

   m_varray[index] -> f = 0;

   m_varray[index] -> dist = 0;

   for (; find != NULL; find = find->ptr) {

      m_varray[find->toid-1] -> dist = find->w;

      m_varray[find->toid-1] -> f = start_point;

   }


   //seek

   for(i = 0; i < MAX_NUM_NODES; i++) { // 최소힙이 비었나로 체크하면 최적화

      struct vertex* v = mindist();  // 최소힙으로 처리하면 최적화

      for (find = v->ptr; find != NULL; find = find->ptr) {

         if (m_varray[find->toid-1]->dist >  v->dist + find-> w) {

            m_varray[find->toid-1]->dist = v->dist + find-> w;

            m_varray[find->toid-1]->f = v->id;

         }

      }

   }

   //done

}


// find edge and add if does not exist

struct edge* add_edge (unsigned int fromid, unsigned int toid,  unsigned int ecost) {

      struct vertex *v;

      struct edge *find;


      if (fromid > MAX_VERTEX_ID || toid > MAX_VERTEX_ID) {

         printf("%s: error, invalid vertex id %d->%d ", __func__, fromid, toid);

         return NULL;

      }


      v = find_vertex(fromid);


      if(v->ptr == NULL){

         v->ptr = (struct edge*)calloc(sizeof(struct edge),1);

         v->ptr->ptr = NULL;

         v->ptr->toid = toid;

         v->ptr->w = ecost;

      }else{

         for(find = v->ptr; find->ptr != NULL; find = find->ptr);      

         find->ptr = (struct edge*)malloc(sizeof(struct edge));

         find->ptr->ptr = NULL;

         find->ptr->toid = toid;

         find->ptr->w = ecost;

      }


}


struct vertex* find_vertex (unsigned int id) {

   struct vertex *v;


   if (id > MAX_VERTEX_ID) {

      printf("%s: error, invalid vertex id %d ", __func__, id);

      return NULL;

   }

   v = m_varray[id-1];

   return v;

}


// find vertex and add if does not exist

struct vertex* add_vertex (unsigned int id) {

   struct vertex *v;


   if (id > MAX_VERTEX_ID) {

      printf("%s: error, invalid vertex id %d ", __func__, id);

      return NULL;

   }

   if ((v = find_vertex(id)) != NULL) {

      return v;

   }


   v = m_varray[id];

   v->id = id;

   v->dist =MAX_DISTANCE;

   v->f = 0;      


   return NULL;    // TODO

}


struct vertex* mindist() {


   int i;

   int min_i = 0;

   int min = 0x7fffffff;    

   for(i=1; i < MAX_NUM_NODES; i++){

      if(min > m_varray[i]->dist && m_varray[i]->on == 1){

         min = m_varray[i]->dist;

         min_i = i;

      }

   }

   m_varray[min_i]->on = 0;

   return m_varray[min_i];


}



int read_input_file(char *filename) {

   FILE *fp;

   char linebuf[1000];

   char linebuf_pro[1000];

   int i=0,j=0,k=0;

   int split =0;

   int splitarr[1000]= {0};

   int fromid=0;

   int toid = 0;

   int ecost = 0;


   m_varray[0] = (struct vertex*)calloc(sizeof(struct vertex) , MAX_NUM_NODES); // memory pool

   for(i= 0; i < MAX_NUM_NODES; i++) {

      m_varray[i+1] = m_varray[i] + 1;

      m_varray[i]->id = i+1;

      m_varray[i]->dist = MAX_DISTANCE;

      m_varray[i]->f = NULL;

      m_varray[i]->ptr = NULL;

      m_varray[i]->on = 1;

   }



   // clear global data before reading the file

   m_n = 0;


   // adjacency list representation of a simple undirected graph

   if ((fp = fopen(filename, "r")) == NULL) {

      perror("Error opening input file ");

      return -1;

   }


   // read data file, line by line

   while (fgets(linebuf, sizeof(linebuf), fp) != NULL) {


      if (m_n > MAX_NUM_NODES) {

         printf("too many data (n = %d) ", m_n);

         break;

      }


      // count tab

     split=0;

      for(i = 1; linebuf[i] != ' ' ; i++){ // kind of seperator 

         if(linebuf[i] == ' ' || linebuf[i] == ',' ){

            split++;

            splitarr[split] = i+1; // position+1 of seperator

         }


      }

      // call sscanf as much as count of tab  

      for (i = 1; i < split; i=i+2)

      {

         int fromid = m_n+1;

         int toid = 0;

         int ecost = 0;

         sscanf(&linebuf[splitarr[i]],"%d" ,&toid); 

         sscanf(&linebuf[splitarr[i+1]],"%d" ,&ecost); 

         add_edge(fromid, toid, ecost);

m_e++;

      }

      m_n++;

   }

   fclose(fp);


   printf("%s: total: %d nodes, %d edges ", __func__, m_n, m_e/2); 


   return 0;


}