1 /*============================================= 2 功能:实现dijkstra算法(单源点路径最短问题) 3 ===============================================*/ 4 5 #include <stdio.h> 6 #include <stdlib.h> 7 8 #define MAX_FLOAT_NUM 100 /* 定义最大浮点数 */ 9 #define TRUE 1 10 #define FALSE 0 11 #define NUM_V 8 /* 邻接表顶点个数 */ 12 13 struct adj_list /* 邻接表节点定义 */ 14 { 15 int v_num; /* 节点编号定义 */ 16 int len; /* 邻接定点与该顶点的距离 */ 17 struct adj_list *next; /* 下一个邻接顶点 */ 18 }; 19 20 typedef struct adj_list NODE; 21 typedef int BOOL; 22 23 void dijkstra(int n, int u); 24 void init(); /* 创建有向图的邻接表 */ 25 void free_memory(); /* 释放内存空间 */ 26 void display(); /* 输出建立的邻接表 */ 27 void display_path(int path[], int distance[], int vetex); /* 最短路径以及距离 */ 28 29 NODE node[NUM_V]; /* 头节点数组 */ 30 31 int array_index[15] = {0,0,0,1,1,2,2,2,2,3,4,5,5,6,6}; 32 int array_length[15] = {1,4,4,2,9,3,6,3,4,7,1,2,5,1,3}; 33 int array_v_num[15] = {1,2,3,2,4,3,4,5,6,6,7,4,7,5,7}; 34 35 int p[23]; 36 int d[23]; 37 38 void main() 39 { 40 init(); 41 display(); 42 dijkstra(23, 0); 43 free_memory(); 44 } 45 /*===================================================== 46 功能:实现dijkstra算法 47 输入:n个节点,源点u 48 输出:顶点到u的距离d[],p[]前方顶点编号 49 =======================================================*/ 50 void dijkstra(int n, int u) 51 { 52 int i = 0,j,t; 53 int temp = MAX_FLOAT_NUM; 54 BOOL *s = malloc(n * sizeof(BOOL)); 55 NODE *pnode = node[u].next; /* 源点邻接表 */ 56 57 if(pnode == NULL) 58 return; 59 60 for(i = 0; i < n; i++) /* 初始化d[] */ 61 { 62 d[i] = MAX_FLOAT_NUM; 63 p[i] = -1; 64 s[i] = FALSE; 65 } 66 s[u] = TRUE; 67 d[u] = 0; 68 p[u] = -1; 69 70 while(pnode) /* 初始化与u点临界点的距离 */ 71 { 72 if(pnode->len < d[pnode->v_num]) 73 { 74 d[pnode->v_num] = pnode->len; 75 p[pnode->v_num] = u; 76 } 77 pnode = pnode->next; 78 } 79 for(i = 0; i < n; i++) 80 { 81 temp = MAX_FLOAT_NUM; 82 t = u; 83 for(j = 0; j < n; j ++) /* 选出d[]中最短路径 */ 84 { 85 if(!s[j] && d[j] < temp) 86 { 87 t = j; 88 temp = d[j]; 89 } 90 } 91 if(t == u) 92 break; /* 找不出最短路径 */ 93 s[t] = TRUE; 94 display_path(p, d, t); /* 显示最短路径和距离 */ 95 pnode = node[t].next; /* 更新与t相连的顶点与原顶点的距离d */ 96 while(pnode) 97 { 98 if(!s[pnode->v_num] && (d[pnode->v_num] > (pnode->len + d[t]))) 99 { 100 d[pnode->v_num] = pnode->len + d[t]; 101 p[pnode->v_num] = t; 102 } 103 pnode = pnode->next; 104 } 105 } 106 free(s); 107 } 108 109 void init() 110 { 111 int i = 0; 112 NODE *end; 113 for(; i < 8; i ++) /* 8个头结点 */ 114 { 115 node[i].v_num = i; 116 node[i].len = 0; 117 node[i].next = NULL; 118 } 119 for(i = 0; i < 15; i ++) 120 { 121 NODE *temp = malloc(sizeof(NODE)); /* 创建一个节点 */ 122 123 temp->len = array_length[i]; 124 temp->next = NULL; 125 temp->v_num = array_v_num[i]; 126 127 end = &node[array_index[i]]; 128 129 while(end->next != NULL) /* 找到邻接表最后一个顶点 */ 130 { 131 end = end->next; 132 } 133 end->next = temp; 134 } 135 } 136 //输出邻接表内容 137 void display() 138 { 139 int i = 0; 140 NODE *end; 141 for(; i < 8; i ++) 142 { 143 end = &node[i]; 144 while(end != NULL) 145 { 146 printf("%d %d ", end->v_num, end->len); 147 end = end->next; 148 } 149 printf(" "); 150 } 151 } 152 //释放邻接表中动态分配的内存空间 153 void free_memory() 154 { 155 NODE *end,*end_behind; 156 int i =0; 157 for(; i < 8; i ++) 158 { 159 end = node[i].next; 160 while(end) 161 { 162 end_behind = end->next; 163 free(end); 164 end = end_behind; 165 } 166 free(end); 167 } 168 } 169 void display_path(int path[], int distance[], int vtex) /* 最短路径以及距离 */ 170 { 171 int i = vtex; 172 printf("path%d:", vtex); 173 174 while(p[i] != -1) 175 { 176 printf("%d ", p[i]); 177 i = p[i]; 178 } 179 printf("distance %d ", distance[vtex]); 180 }