【原】图

 1 #ifndef _DIJKSTRA_H_
 2 #define _DIJKSTRA_H_
 3 
 4 #include<sys/types.h>
 5 #include<stdio.h>
 6 #include<string.h>
 7 #include<ctype.h>
 8 
 9 #define bool   unsigned char
10 #define TRUE   (1)
11 #define FALSE  (0)
12 
13 #define VER_NUM  7
14 #define MAX_QUEUE_SIZE  100
15 
16 typedef int ELEMENT_TYPE;
17 
18 typedef struct
19 {
20     int front;
21     int rear;
22     int size;
23     ELEMENT_TYPE array[MAX_QUEUE_SIZE];
24 }QUEUE;
25 
26 typedef struct ver_edge
27 {
28     int weight;
29     int to;
30     struct ver_edge* next;
31 }VER_EDGE;
32 
33 typedef struct 
34 {
35     VER_EDGE* ver_edge;
36     bool known;
37     int dis;
38     int pre_verx;
39 }VERTEX;
40 
41 #endif

 1 #include "dijkstra.h"
 2 
 3 static QUEUE* ver_queue ;
 4 
 5 static VERTEX* vertexs;/* garph is vertexs*/
 6 
 7 void init_verQueue()
 8 {
 9     ver_queue = (QUEUE*)malloc(sizeof(QUEUE));
10     ver_queue->front = 0;
11     ver_queue->rear = 0;
12     ver_queue->array = 0;
13     ver_queue->size = 0;
14 }
15 
16 bool is_queue_empty(QUEUE* queue)
17 {
18     return 0 == queue->size;
19 }
20 
21 void en_queue(QUEUE* queue,ELEMENT_TYPE element)
22 {
23     if(queue->size = MAX_QUEUE_SIZE)
24     {
25         printf("enqueue fail!
");
26         return ;
27     }
28     queue->array[queue->rear++] = element;
29     queue->size++;
30 }
31 
32 ELEMENT_TYPE* queue_front(QUEUE* queue)
33 {
34     if( queue->size == 0)
35     {
36         printf("get front fail!
");
37         return ;
38     }
39     return (queue->array + queue->front);
40 }
41 
42 void de_queue(QUEUE* queue)
43 {
44     if(is_queue_empty(queue))
45     {
46         printf("dequeue fail!
");
47         return ;
48     }
49     queue->front++;
50 }
51 
52 
53 void init_vertex()
54 {
55     int i = 0;
56     vertexs = (VERTEX*)malloc(VER_NUM*sizeof(VERTEX));
57     for( i = 0;i< VER_NUM;i++)
58     {
59         vertexs[i].ver_edge = NULL;
60     }
61 }
62 void insert_edge(int from,int to,int weight)
63 {
64     int i = from -1;
65     VER_EDGE* temp = (VER_EDGE*)malloc(sizeof(VER_EDGE));
66     temp->next = NULL;
67     temp->weight = weight;
68     temp->to = to;
69 
70     temp->next = vertexs[i].ver_edge;
71     vertexs[i].ver_edge= temp;
72 }
73 
74 /*for graph that has a circle:
75 how to choose the vertex is a problem,can use foreach or priority queue; 
76 for acyclic graph: 
77 use the topological order to get the vertex in loop;
78 */
79 
80 /*算法: 选点、设为known、更新边*/
81 void dijkstra(int init_ver, VERTEX* vertexs)
82 {
83     
84 }