重复造轮子系列--dijkstra算法

前年一时脑热（理想很丰满，现实很骨感），写了这个最短路径优先的低效版本，且留着回忆吧。

spf.h

 1 #ifndef SPF_H_
 2 #define SPF_H_
 3 
 4 
 5 typedef struct {
 6     int length;
 7     char src;
 8     char dst;
 9     char prev_hop;
10 } dijkstra; 
11 
12 #define MAX 1024
13 #define NODE_NUM 5
14 #define TRUE 1
15 #define FALSE 0
16 
17 #endif

spf.c

  1 #include <stdio.h>
  2 #include <stdarg.h>
  3 #include <string.h>
  4 #include <limits.h>
  5 #include <time.h>
  6 #include <sys/timeb.h>
  7 #include "spf.h"
  8 
  9 dijkstra DIJK[NODE_NUM][NODE_NUM] = {0};
 10 char NODES[NODE_NUM] = {'A', 'B', 'C', 'D', 'E'};
 11 int P_NDS[NODE_NUM] = {0};
 12 int U_NDS[NODE_NUM] = {0};
 13 
 14 int distance(char src, char dst);
 15 void debug(char* fmt,...);
 16 void spf_dijkstra_init();
 17 void spf_show_dijkstra_matrix(int top);
 18 dijkstra* spf_shortest_path_cost(char src, char dst);
 19 void spf_main(int src_top);
 20 int in_pnd_sets(char src);
 21 void spf_pu_sets_init();
 22 int spf_find_candidate_node(int src_top, int top);
 23 int spf_calc_next_hop(int src_top, int top, int min_idx);
 24 void time_show();
 25 
 26 int main(int argc, char **argv) {
 27     int i;
 28     //time_show();
 29     spf_dijkstra_init();
 30     for (i=0; i<NODE_NUM; i++) {
 31         spf_pu_sets_init();
 32         spf_main(i);
 33         //spf_show_dijkstra_matrix(i);
 34     }
 35     //time_show();
 36     return 0;
 37 }
 38 
 39 void spf_pu_sets_init() {
 40     memset(P_NDS, 0, sizeof(P_NDS));
 41     memset(U_NDS, 0, sizeof(U_NDS));
 42 }
 43 
 44 void spf_main(int src_top) {
 45     int top = src_top;
 46     int min_node_id = -1;
 47     int loop = 0;
 48     
 49     if (top >= NODE_NUM || top < 0) {
 50         debug("input error src_top = %d, input again plz 
");
 51         return;
 52     }
 53  
 54     P_NDS[top] = TRUE;
 55     while(TRUE) {
 56         if (loop == NODE_NUM) break;
 57         loop++;
 58 
 59         min_node_id = spf_find_candidate_node(src_top, top);
 60         if (min_node_id == -1) continue;
 61         top = spf_calc_next_hop(src_top, top, min_node_id);
 62         if (top<0 || top>NODE_NUM) continue;
 63         P_NDS[top] = TRUE;      
 64     }
 65     return;
 66 }
 67 
 68 int spf_find_candidate_node(int src_top, int top) {
 69     int min_idx = -1;
 70     int min_cost = MAX;
 71 
 72     for (int i=0; i<NODE_NUM; i++) {
 73         if (TRUE == P_NDS[i]) continue;  // 已经计算过路由的就不在计算   
 74                                      
 75         int d1 = distance(NODES[top], NODES[i]);
 76         if (MAX == d1 || 0 == d1) continue;
 77 
 78         U_NDS[i] = TRUE;
 79         dijkstra* dij_dst = spf_shortest_path_cost(NODES[src_top], NODES[i]);
 80         dijkstra* dij_hop = spf_shortest_path_cost(NODES[src_top], NODES[top]);
 81 
 82         if (NULL == dij_dst || NULL == dij_hop) continue;
 83 
 84         // 如果源顶点与当前节点的距离 > 源顶点与当前顶点的距离 + 当前顶点与当前节点的距离，
 85         // 则设置当前顶点为当前节点的上一跳节点
 86         // 'S' 表示没有设置过上一跳节点
 87         if (dij_dst->length > d1+dij_hop->length || dij_dst->prev_hop == 'S') {
 88             dij_dst->prev_hop = NODES[top];
 89         }
 90 
 91         if (d1 < min_cost) {
 92             min_cost = d1;
 93             min_idx = i;            
 94         }
 95     }
 96 
 97     return min_idx;
 98 }
 99 
100 int spf_calc_next_hop(int src_top, int top, int min_idx) {
101     for (int i=0; i<NODE_NUM; i++) {
102         if (FALSE == U_NDS[i]) continue;
103         int d1 = distance(NODES[src_top], NODES[i]); 
104         int d2 = distance(NODES[top], NODES[i]); 
105 
106         if (0 == d2) continue;           
107         dijkstra* dij_top = spf_shortest_path_cost(NODES[src_top], NODES[top]);   
108         int d3 = d2 + dij_top->length;    
109         dijkstra* dij_dst = spf_shortest_path_cost(NODES[src_top], NODES[i]);
110         if (!dij_dst) continue;
111 
112         // 如果源顶点到当前节点的已经过计算的最短路径距离小于直接计算源顶点与当前节点距离
113         //，则使用最短路径距离
114         if (dij_dst->length < d1) d1 = dij_dst->length;                 
115 
116         // 如果源顶点与当前顶点的距离+当前顶点到当前节点的距离
117         // 小于直接计算源顶点与当前节点距离，
118         // 则把当前顶点设置为当前的节点上一跳
119         if (0 < d3 && d3 < MAX && d3 <= d1) {
120             dij_dst->prev_hop = NODES[top];
121             dij_dst->length = d3;
122             U_NDS[i] = FALSE;          
123         } 
124         // 如果当前节点的最短路径距离小于当前顶点计算的距离，
125         // 则调整当前节点上一跳，重新开始最短路由运算
126         else if (d1 > 0 && d1 < d3 && d3 < MAX) { 
127             int d = distance(dij_dst->src, dij_dst->dst);
128             // 如果源顶点与目标节点是直连，并且距离小于最短路径距离，
129             // 则设置上一条节点为源顶点
130             if (MAX!=d && d<dij_dst->length) 
131                 dij_dst->prev_hop = dij_dst->src;                
132 
133             P_NDS[top] = FALSE;
134             U_NDS[top] = TRUE;
135             min_idx = i;            
136         }           
137     }
138     return min_idx;
139 }
140 
141 int in_pnd_sets(char src) {
142     int i;
143     for (i=0; i<NODE_NUM; i++)
144         if (NODES[i] == src && P_NDS[i] == TRUE)
145             return TRUE;
146     return FALSE;
147 }
148 
149 void spf_dijkstra_init() {
150     int i,j;
151     for (i=0; i<NODE_NUM; i++) {
152         for (j=0; j<NODE_NUM; j++) {
153             DIJK[i][j].length = distance(NODES[i], NODES[j]);
154             DIJK[i][j].src = NODES[i];
155             DIJK[i][j].dst = NODES[j];    
156             DIJK[i][j].prev_hop = DIJK[i][j].length == 0 ? NODES[i] : 'S';   
157         }
158     }
159     return;
160 }
161 
162 void spf_show_dijkstra_matrix(int top) {
163     int i,j;
164     for (i=0; i<NODE_NUM; i++) {
165         for (j=0; j<NODE_NUM; j++) {
166             if (top == i && DIJK[i][j].src != DIJK[i][j].dst)
167                 printf("len=%d src=%c dst=%c prev=%c
", 
168                 DIJK[i][j].length, DIJK[i][j].src,
169                 DIJK[i][j].dst, DIJK[i][j].prev_hop);
170         }        
171     }
172     printf("
");
173     return;
174 }
175 
176 dijkstra* spf_shortest_path_cost(char src, char dst) {
177     dijkstra* dij = &DIJK[0][0];
178     for (int k=0; k<NODE_NUM*NODE_NUM; k++,dij++) {
179         if (dij->src == src && dij->dst == dst) 
180             return dij;
181     }
182 
183     return NULL;
184 }
185 
186 int distance(char src, char dst) {
187     if (src == dst) return 0;
188     if ('A' == src && 'B' == dst) return 1;
189     if ('B' == src && 'A' == dst) return 1;
190     if ('A' == src && 'C' == dst) return 5;
191     if ('C' == src && 'A' == dst) return 5;    
192     if ('B' == src && 'D' == dst) return 6;
193     if ('D' == src && 'B' == dst) return 6;
194     if ('B' == src && 'E' == dst) return 2;
195     if ('E' == src && 'B' == dst) return 2;
196     if ('C' == src && 'E' == dst) return 1;
197     if ('E' == src && 'C' == dst) return 1;
198     if ('D' == src && 'E' == dst) return 1;
199     if ('E' == src && 'D' == dst) return 1;
200     return MAX;
201 }